More content：LeetCode hot100@二叉树

257. 二叉树的所有路径❌

递归回溯

递归三步走，但要注意在二叉树的递归中单层逻辑一般要包括中左右三部分（顺序依前中后遍历而定）

class Solution {
public:
    void traversal(TreeNode *cur, vector<string> &res, vector<int> &path) {
        //因为调用递归时没有处理root 所以要先处理一下当下节点 后两题则不同
        path.push_back(cur->val); //单层逻辑部分 中

        //终止条件不会是空节点 因为空节点根本无法进入递归
        if(!cur->left && !cur->right) { //遇到叶子节点 意味着一条路径
            string s;
            for(int i = 0; i < path.size() - 1; i++) {
                s += to_string(path[i]); //将整型转换为字符串
                s += "->";
            }
            s += to_string(path[path.size()-1]);
            res.push_back(s);
            return ;
        } 

        if(cur->left) { //单层逻辑部分 左
            traversal(cur->left, res, path);
            path.pop_back(); //回溯！
        }
        if(cur->right) { //单层逻辑部分 右
            traversal(cur->right, res, path);
            path.pop_back(); //回溯！
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        vector<int> path; //记录路径节点val
        
        traversal(root, res, path);

        return res;
    }
};

---

112. 路径总和❌

递归回溯 想清楚返回false回溯的过程

class Solution {
public:
    bool travseral(TreeNode* cur, int sum) {
        //终止条件
        if(!cur->left && !cur->right && !sum) return true;
        if(!cur->left && !cur->right) return false;
        
        if(cur->left) {
            sum -= cur->left->val;
            //用于终止条件第二行的判断 如果返回false 就直接回溯
            if(travseral(cur->left, sum)) return true;
            sum += cur->left->val; //回溯
        }
        if(cur->right) {
            sum -= cur->right->val;
            if(travseral(cur->right, sum)) return true;
            sum += cur->right->val; //回溯
        }

        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        //用减取代加 可以少传递一个参数
        return travseral(root, targetSum - root->val); 

    }
};

---

113. 路径总和 II✅

257.二叉树的所有路径 + 112. 路径总和

class Solution {
public:
    void travseral(TreeNode *cur, vector<vector<int>> &res, vector<int> &path, int sum) {
        if(!cur->left && !cur->right && !sum) res.push_back(path);
        if(!cur->left && !cur->right) return ;

        if(cur->left) {
            sum -= cur->left->val;
            path.push_back(cur->left->val);
            travseral(cur->left, res, path, sum);
            sum += cur->left->val;
            path.pop_back();
        }
        if(cur->right) {
            sum -= cur->right->val;
            path.push_back(cur->right->val);
            travseral(cur->right, res, path, sum);
            sum += cur->right->val;
            path.pop_back();
        }

        return ;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;
        if(!root) return res;
        //先把root数据处理好（包括path和下面的sum）
        //这样到了递归里就只关心左和右节点 而不用管当下节点 理清单层逻辑
        path.push_back(root->val); 
        travseral(root, res, path, targetSum - root->val);

        return res;
    }
};

---

106. 从中序与后序遍历序列构造二叉树❌

递归构造

注意确定左闭右开的原则后 要贯彻整个代码

class Solution {
public:
    TreeNode* traversal(vector<int> &inorder, int inorderBegin, int inorderEnd, vector<int> &postorder, int postorderBegin, int postorderEnd) {
        if(inorderBegin == inorderEnd) return nullptr;

        int root_val = postorder[postorderEnd - 1];
        TreeNode *root = new TreeNode(root_val);
        if(postorderEnd - postorderBegin == 1) return root;

        int cutIndex = 0;
        //一直贯彻左闭右开
        for(cutIndex = inorderBegin; cutIndex < inorderEnd; cutIndex++) {
            if(inorder[cutIndex] == root_val) break;
        }
        
        //切割中序数组 舍弃中间那个节点
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = cutIndex;
        int rightInorderBegin = cutIndex + 1;
        int rightInorderEnd = inorderEnd;

        //切割后序数组 舍弃最后那个节点
        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin + leftInorderEnd - leftInorderBegin;
        int rightPostorderBegin = postorderBegin + leftInorderEnd - leftInorderBegin;
        int rightPostorderEnd = postorderEnd - 1;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
        
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

---

700. 二叉搜索树中的搜索✅

简单

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return nullptr;

        if(root->val == val) return root;
        else if(root->val > val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }

    }
};

---

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

模拟一下就有思路了 只要是BST 一般都是中序遍历 不然有序还有什么用

class Solution {
private:
    int sum; //所有节点之和
public:
    void sumTravseral(TreeNode *cur) {  
        sum += cur->val;
        if(cur->left) sumTravseral(cur->left);
        if(cur->right) sumTravseral(cur->right); 
    }
    void changeTravseral(TreeNode *cur) { //BST 因此中序遍历 累加值递减
        if(cur->left) changeTravseral(cur->left); //左

        int tmp = cur->val;
        cur->val = sum; //中
        sum -= tmp;

        if(cur->right) changeTravseral(cur->right); //右
    }
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return root;

        sumTravseral(root);
        changeTravseral(root);
        
        return root;
    }
};

---

236. 二叉树的最近公共祖先❌

从目标节点开始自底向上回溯（只能后序）一层层传过去

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        //找某一条路径就要在递归中及时return，而遍历整棵树就像下面这样用
        //节点来承接，递归完统一处理左右两个递归，即处理后序遍历的中间节点
        //遍历整个树不代表要把每个点都处理 比如示例一搜了三个点就返回了
        //但如果p q都是叶子节点 那就要搜完整棵树了 比如代码随想录的示例图
        TreeNode *left = lowestCommonAncestor(root->left, p, q); //左
        TreeNode *right = lowestCommonAncestor(root->right, p, q); //右
        //中:
        //这里return的就是左右两棵子树各一个p q 当下的root就是最近公共祖先
        if(left && right) return root; 
        //这里return的就是左右两棵子树最多有一棵搜到了p和q 继续往上传递直到根节点  
        if(!left && right) return right;
        else if(left  && !right) return left;
        else return nullptr;
    }
};

---

235. 二叉搜索树的最近公共祖先✅❌

可以直接copy上题236. 二叉树的最近公共祖先代码后序遍历 因为BST也是二叉树嘛 但就浪费了BST的有序性 所以二分着去搜

如果找到一个节点值位于pq之间 那么这个节点一定是pq的公共祖先 而且就是最近的 所以不需要像上题一样遍历整棵树 找到节点直接返回即可

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if(!cur) return nullptr;
                                                       
        if(cur->val > p->val && cur->val > q->val) { //左
            TreeNode* left = lowestCommonAncestor(cur->left, p, q);
            if(left) return left;
        }

        if(cur->val < p->val && cur->val < q->val) { //右
            TreeNode* right = lowestCommonAncestor(cur->right, p, q);
            if(right) return right;
        }

        return cur;
    }
};

---

701. 二叉搜索树中的插入操作✅

想一下搜到什么情况下插入

class Solution {
public:
    void travseral(TreeNode *cur, int val) {
        if(cur->val < val) {
            if(cur->right) travseral(cur->right, val);
            else {
                cur->right = new TreeNode(val);
                return ;
            }
        }
        if(cur->val > val) {
            if(cur->left) travseral(cur->left, val);
            else {
                cur->left = new TreeNode(val);
                return ;
            }
        }
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        travseral(root, val);
        return root;
    }
};

---

669. 修剪二叉搜索树❌

思路有点难想 怎么实现的节点移除 怎么接住返回的节点

class Solution {
public:
    TreeNode* trimBST(TreeNode* cur, int low, int high) {
        if(!cur) return nullptr;

        if(cur->val > high) { //超出上限 去左边找符合区间的子树来替代cur
            return trimBST(cur->left, low, high);
        }
        if(cur->val < low) { //低于下限 去右边找符合区间的子树来替代cur
            return trimBST(cur->right, low, high);
        }

        cur->left = trimBST(cur->left, low, high); //接住下一层符合区间的子树
        cur->right = trimBST(cur->right, low, high);

        return cur;
    }
};