1.二叉搜索树中第k小的元素

给定二叉搜索树的根节点root，和一个整数k，设计一个算法查找其中第k小的元素(从1开始计数)

BST 的中序遍历结果是有序的（升序），所以用一个外部变量记录中序遍历结果第 k 个元素即是第 k 小的元素。

class Solution {
private:int res = 0;int rank = 0;void traverse(TreeNode* root, int k){if(root == nullptr) return;traverse(root->left, k);//中序位置rank ++;if(rank == k){res = root->val;return;}traverse(root->right, k);}
};
public:int kthSmallest(TreeNode* root, int k) {traverse(root, k);return res;
}

2.删除给定值的叶子节点

给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。

注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。

也就是说，你需要重复此过程直到不能继续删除。

遍历所有叶子节点，然后判断是否需要删除即可，删除叶子节点也非常简单，return null让父节点接受即可，难点在于删除操作是循环的，一直删到叶子结点不存在target为止。
这里涉及到后序遍历，一个节点在后序位置接受左右子树的返回值，才能知道自己的叶子节点是否都被删除掉了，以此来判断自己是不是变成了叶子节点

class Solution {
public:TreeNode* removeLeafNodes(TreeNode* root, int target) {if(root == nullptr) return nullptr;// 如果左右子节点需要被删除，先递归删除它们root->left = removeLeafNodes(root->left, target);root->right = removeLeafNode(root->right, target); // 后序遍历位置，此时节点 root 直到自己是否需要被删除//如果当前节点是一个叶子节点并且其值等于 target，则通过返回 nullptr 来告诉调用它的父节点函数，这个节点应该被删除。//这意味着在父节点中，指向这个被删除节点的指针（left 或 right）将被设置为 nullptr。if(root->val == target && root->left == nullptr && root->right == nullptr)return root;}
};

3.把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树，使每个节点node的新值等于原树种大于或等于node.val的值之和。

求树中大于等于该节点值的所有节点的总和
8,8+7=15，15+6=21，21+5=26，右中左

class Solution {
public:int sum = 0;TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;convertBST(root->right);root->val += sum;sum = root->val;convertBST(root->left);return root;}
};

4.合并二叉树

给你两棵二叉树root1和root2。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

可以看做是在遍历root1这一棵二叉树，顺便把root2的节点合并过来。

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == nullptr) return root2;if(root2 == nullptr) return root1;root1->val += root2->val;root1->left = mergeTrees(root1->left, root2->left);root1->right = mergeTrees(root1->right, root2->right);return root1;}
};    

5.翻转二叉树

给你一棵二叉树的根节点，翻转这棵二叉树，并返回其根节点。

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root == nullptr){return nullptr;}invertTree(root->left);invertTree(root->right);TreeNode* tmp = root->right;root->right = root->left;root->left = tmp;return root;}
};

6.二叉树中所有距离为k的节点

给定一个二叉树，具有根节点root，一个目标节点target，和一个整数值k，返回到目标节点target距离为k的所有节点的值的数组。
其中树上所有节点的值val是不同的

parent来记录当前节点

class Solution {
private:void traverse(TreeNode* root, TreeNode* parentNode){if(root == nullptr) return;parent[root->val] = parentNode;traverse(root->left, root);traverse(root->right, root);}
public:unordered_map<int, TreeNode*> parent;vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {traverse(root, nullptr);queue<TreeNode*> q;q.push(target);unordered_set<int> visited;visited.insert(target->val);int dist = 0;vector<int> res;while(!q.empty()){int size = q.size();for(int i = 0; i < size; i ++){TreeNode* cur = q.front();q.pop();if(dist == k){res.push_back(cur->val);}//向父节点，左孩子节点，右孩子节点三个方向扩散TreeNode* parentNode = parent[cur->val];if(parentNode != nullptr && visited.find(parentNode->val) == visited.end()){visited.insert(parentNode->val);q.push(parentNode);}if(cur->left != nullptr && visited.find(cur->left->val) == visited.end()){visited.insert(cur->left->val);q.push(cur->left);}if(cur->right != nullptr && visited.find(cur->right->val) == visited.end()){visited.insert(cur->right->val);q.push(cur->right);}}dist ++;}return res;}
};	

7.路径总和II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

遍历的思维很简单，只要遍历一遍二叉树，就可以把所有符合条件的路径找出来。为了维护经过的路径，在进入递归的时候要在 path 列表添加节点，结束递归的时候删除节点。

class Solution {
private:vector<vector<int>> res;void traverse(TreeNode* root, vector<int> path, int targetSum){if(root == nullptr) return;int remain = targetSum - root->val;//找到了一条路径if(root->left == nullptr && root->right == nullptr){if(remain == 0){path.push_back(root->val);res.push_back(path);path.pop_back();}return;//继续找}//维护路径列表path.push_back(root->val);traverse(root->left, path, remain);path.pop_back();path.push_back(root->val);traverse(root->right, path, remain);path.pop_back();}
public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == nullptr) return res;traverse(root, vector<int>(), targetSum);return res;}
};

8.寻找重复的子树

给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。

如果想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，需要知道什么信息？上面的的[2, 4]其实是返回了以2为根节点的TreeNode型
需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？-> 需要在后序的位置进行操作

2、以其他节点为根的子树都长啥样？-> 前序后序层序都可以反映二叉树的结构(中序不行)，所以可以将二叉树序列化

class Solution {
private:vector<TreeNode*> res;unordered_map<string, int> subTree;string serialize(TreeNode* root){if(root == nullptr) return "#";string left = serialize(root->left);string right = serialize(root->right);string myself = left + ',' + right + ',' + to_string(root->val);int freq = subTree[myself];if(freq == 1){res.push_back(root);}subTree[myself]++;return myself;//随便返回的,需要一个返回值}
public:vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {serialize(root);return res;}
};

9.二叉树的序列化和反序列化

序列化和39是一个意思，反序列化就是给一串string字符串，将其还原成树。

什么样的序列化数据可以反序列化出唯一的一颗二叉树？只要给了空指针信息，前后序层序就可以缺点唯一的二叉树
代码以前序为例

class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {if (!root) return "#";return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {vector<string> nodes;string cur = "";//过滤掉逗号for (char c : data) {if (c == ',') {nodes.push_back(cur);cur = "";} else {cur += c;}}if (!cur.empty()) nodes.push_back(cur); // Add the last nodeint index = 0;return deserialize(nodes, index);}TreeNode* deserialize(vector<string>& nodes, int& index) {if (index >= nodes.size() || nodes[index] == "#") {index++;return nullptr;}TreeNode* root = new TreeNode(stoi(nodes[index++]));root->left = deserialize(nodes, index);root->right = deserialize(nodes, index);return root;}
};