Binary Tree_Leetcode

作者： /

下一个部份刷题开启🔛

⚠️注意二叉树的class类

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
    TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right){}
};

144. Binary Tree Preorder Traversal

Solution 1: #Recursion

class Solution {
public:
    vector<int> ans;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root){
            ans.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return ans;
    }
};

Solution 2: #Iterative

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        while(root || !st.empty()){
            if(root){
                ans.push_back(root->val);
                st.push(root->right);
                root = root->left;
            }
            else{
                root = st.top();
                st.pop();
            }
        }
        return ans;
    }
};

145. Binary Tree Postorder Traversal

Solution 1: #Recursion

class Solution {
public:
    vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(root){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            ans.push_back(root->val);
        }
        return ans;
    }
};

Solution 2: #Iterative

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == nullptr) return ans;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            if(cur->left){
                st.push(cur->left);
                cur->left = NULL;
            }
            else{
                if(cur->right){
                    st.push(cur->right);
                    cur->right = NULL;
                }
                else{
                    ans.push_back(cur->val);
                    st.pop();
                }
            }
        }
        return ans;
    }
};

94. Binary Tree Inorder Traversal

Solution 1: #Recursion

class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root){
            inorderTraversal(root->left);
            ans.push_back(root->val);
            inorderTraversal(root->right);
        }
        return ans;
    }
};

Solution 2: #Iterative

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        while(root || !st.empty()){
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            ans.push_back(root->val);
            root = root->right;
        }
        return ans;
    }
};

102. Binary Tree Level Order Traversal

Solution 1:#queue，#BFS，就是用队列来模拟一层一层的往下遍历；非常重要的层序遍历❗️

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        vector<vector<int>> ans;
        while(!que.empty()){
            int n = que.size(); // n stands for the number of node in each level
            vector<int> vec;   // vec is to collect the node's value in each level
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                // collect the child node for the next loop
                if(node->left) que.push(node->left);     
                if(node->right) que.push(node->right);
            }
            ans.push_back(vec);     // all nodes in the same level are collected
        }
        return ans;
    }
};

Solution 2: #Recursion，#DFS，不断的递归下去，有一点点难以理解

class Solution {
public:
    void DFS(vector<vector<int>>& res, TreeNode* root, int level){
        if(!root) return;
    //如果当前层级level等于结果数组res的大小，表示当前层级还没有对应的子数组，因此需要添加一个空的子数组。
        if(res.size() == level) res.push_back(vector<int>{});
        res[level].push_back(root->val);
        DFS(res, root->left, level + 1);
        DFS(res, root->right, level + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        DFS(res, root, 0);
        return res;
    }
};

107. Binary Tree Level Order Traversal II

Solution 1: #queue, #BFS, 就是上一题的层序遍历最后把容器翻转一下

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        vector<vector<int>> ans;
        while(!que.empty()){
            int n = que.size();
            vector<int> vec;
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right); 
            }
            ans.push_back(vec);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Solution 2: #Recursion, #DFS，也是用上一题的递归然后翻转容器

class Solution {
public:
    void DFS(vector<vector<int>>& ans, TreeNode* root, int level){
        if(!root) return;
        if(ans.size() == level) ans.push_back({});
        ans[level].push_back(root->val);
        DFS(ans, root->left, level + 1);
        DFS(ans, root->right, level + 1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        DFS(ans, root, 0);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Solution 3: 方法2的一个优化，免去了翻转容器和对内存空间的优化

class Solution {
public:
    // use recursion to find the depth of the tree
    int depth(TreeNode* root){
        if(!root) return 0;
        return max(depth(root->left), depth(root->right)) + 1;    
    }
    void DFS(vector<vector<int>>& ans, TreeNode* root, int level){
        if(!root) return;
        ans[level].push_back(root->val);
        DFS(ans, root->left, level - 1);
        DFS(ans, root->right, level - 1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        int d = depth(root);
        vector<vector<int>> ans(d, vector<int>{});
        DFS(ans, root, d - 1);
        return ans;
    }
};

199. Binary Tree Right Side View

Solution 1:#BFS, #Queue,这道题真的很迷惑，收集的是每一层最靠右边的节点，而不是一直向右递归

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        vector<int> ans;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            for(int i = 0; i < n; i++){
                TreeNode* node = que.front();
                que.pop();
                if(i == n - 1) ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return ans;
    }
};

Solution 2: #Recursion，改进的DFS

class Solution {
private:
    void rightSearch(vector<int>& ans, TreeNode* root, int level){
        if(!root) return;
        if(ans.size() == level) ans.push_back(root->val);  // collect node in the current level
        rightSearch(ans, root->right, level + 1);    // to collect the rightmost node
        rightSearch(ans, root->left, level + 1);
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        rightSearch(ans, root, 0);
        return ans;
    }
};

637. Average of Levels in Binary Tree

#Solution 1: #Queue, #BFS

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        vector<double> ans;
        while(!que.empty()){
            int n = que.size(); // the number of nodes in the current level 
            double sum = 0;
            for(int i = 0; i < n; i++){
                TreeNode* node = que.front();// take the node one by one in the current level
                que.pop();
                sum += node->val;
                if(node->left) que.push(node->left); // collect the child node for next loop
                if(node->right) que.push(node->right);
            }
            ans.push_back(sum / n);
        }
        return ans;
    }
};

#Solution 2: #Recursion, #DFS

class Solution {
public:
    // pair分别对应当前level的和，和高度
    void DFS_count(TreeNode* root, vector<pair<double, double>>& ve, int level){
        if(root == NULL) return;
        if(ve.size() == level) ve.push_back({0, 0});   // a new level begin;
        ve[level].first += root->val;
        ve[level].second += 1;
        DFS_count(root->left, ve, level + 1);
        DFS_count(root->right, ve, level + 1);
    }
    vector<double> averageOfLevels(TreeNode* root) {
        vector<pair<double, double>> ve;
        DFS_count(root, ve, 0);
        vector<double> ans;
        for(int i = 0; i < ve.size(); i++) ans.push_back(ve[i].first / ve[i].second);
        return ans;
    }
};

429. N-ary Tree Level Order Traversal

Solution 1: # BFS, # Queue

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        if(root != nullptr) que.push(root);
        vector<vector<int>> ans;
        while(!que.empty()){
            int n = que.size(); // number fo nodes in the current level
            vector<int> v;    // collect the node in the current level
            for(int i = 0; i < n; i++){
                Node* node = que.front();
                que.pop();
                v.push_back(node->val);
                for(int i = 0; i < node->children.size(); i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
            ans.push_back(v);
        }
        return ans;
    }
};

Solution 2: #DFS, #Recursion

class Solution {
private:
    void DFS(Node* root, vector<vector<int>>& ans, int level){
        if(root == NULL) return;
        if(level >= ans.size()) ans.push_back({});
        ans[level].push_back(root->val);
        for(auto it : root->children){
            DFS(it, ans, level + 1);
        }
    }
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        DFS(root, ans, 0);
        return ans;
    }
};

515. Find Largest Value in Each Tree Row

Solution 1: #BFS, #Queue

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        vector<int> ans;
        while(!que.empty()){
            int n = que.size();
            int d = INT_MIN;
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                d = max(d, node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(d);
        }
        return ans;
    }
};

Solution 2:#DFS, #Recursion

class Solution {
public:
    void DFS(TreeNode* root, vector<int>& ans, int level){
        if(root == nullptr) return;
        if(ans.size() < level + 1) ans.push_back(root->val);
        else{
            if(root->val > ans[level]) ans[level] = root->val;
        }
        DFS(root->left, ans, level + 1);
        DFS(root->right, ans, level + 1);
    }
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        DFS(root, ans, 0);
        return ans;
    }
};

116. Populating Next Right Pointers in Each Node

Solution 1: #BFS, #Queue

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int n = que.size();
            for(int i = 0; i < n; i++){
                Node* cur = que.front();
                que.pop();
                if(i == n - 1) cur->next = nullptr;
                else cur->next = que.front(); // 不是最后一个元素那么就指向队列的头元素
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

Solution 2: #DFS, #Recursion

class Solution {
public:
    void DFS(Node* root, vector<Node*>& collect, int cur_level){ // 注意引用传递
        if(!root) return;
        if(collect.size() == cur_level) collect.push_back(root); // 当前level第一次出现
        else{
            collect[cur_level]->next = root;    // 第二次出现之后的情况，模拟一个类似栈的过程
            collect[cur_level] = root;
        }
        DFS(root->left, collect, cur_level + 1);
        DFS(root->right, collect, cur_level + 1);
    }
    Node* connect(Node* root) {
        vector<Node*> collect;
        DFS(root, collect, 0);
        return root;
    }
};

117. Populating Next Right Pointers in Each Node II

Solution 1: #BFS, #Queue, 跟上一题一样

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            for(int i = 0; i < n; i++){
                Node* cur = que.front();
                que.pop();
                if(i == n - 1) cur->next = nullptr;
                else cur->next = que.front();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

Solution 2: # DFS, #Recursion

class Solution {
public:
    void DFS(Node* root, vector<Node*>& collect, int level){
        if(!root) return;
        if(collect.size() == level) collect.push_back(root);
        else{
            collect[level]->next = root;
            collect[level] = root;
        }
        DFS(root->left, collect, level + 1);
        DFS(root->right, collect, level + 1);
    }
    Node* connect(Node* root) {
        vector<Node*> collect;
        DFS(root, collect, 0);
        return root;
    }
};

104. Maximum Depth of Binary Tree

Solution 1: #BFS, #Queue

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int height = 0;
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            height++;
        }
        return height;
    }
};

Solution 2: #DFS, #Recursion

class Solution {
public:
    int DFS_helper(TreeNode* root, int level){
        if(!root) return level;
        int left_height = DFS_helper(root->left, level + 1);
        int right_height = DFS_helper(root->right, level + 1);
        return max(left_height, right_height);
    }
    int maxDepth(TreeNode* root) {
        return DFS_helper(root, 0);
    }
};

111. Minimum Depth of Binary Tree

Solution 1: #BFS, #Queue

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int min_height = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            min_height++;
            while(n--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                if(cur->left == nullptr && cur->right == nullptr) return min_height;
            }
        }
        return 0;
    }
};

Solution 2: #DFS, #Recursion

class Solution {
public:
    int dfs_helper(TreeNode* root){
        if(!root) return INT_MAX;   // 空节点
        if(!root->left && !root->right) return 1;
        return 1 + min(dfs_helper(root->left), dfs_helper(root->right));

    }
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        return dfs_helper(root);
    }
};

226. Invert Binary Tree

#Solution 1: #BFS, #Queue

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

Solution 2: #Recursion

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

101. Symmetric Tree

Solution 1: #Recursion ⚠️要把终止条件一一判明了再递归下去❗️❗️

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        if(left == nullptr && right) return false;
        else if(left && right == nullptr) return false;
        else if(left == nullptr && right == nullptr) return true;
        else if(left->val != right->val) return false;
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool isSame = outside && inside;
        return isSame;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

Solution 2: #Iterative，#Stack

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        stack<TreeNode*> st;
        st.push(root->left);
        st.push(root->right);
        while(!st.empty()){
            TreeNode* r = st.top(); st.pop();
            TreeNode* l = st.top(); st.pop();
            if(!r && !l) continue;
            if(r == nullptr || l == nullptr || l->val != r->val) return false;
            st.push(l->left);
            st.push(r->right);
            st.push(l->right);
            st.push(r->left);
        }
        return true;
    }
};

100. Same Tree

Solution 1: #Recursion ⚠️一定要判断好了终止条件之后才往下递归🌽

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) return true;
        else if(p == nullptr && q) return false;
        else if(p && q == nullptr) return false;
        else if(p->val != q->val) return false;
        bool leftSame = isSameTree(p->left, q->left);
        bool rightSame = isSameTree(p->right, q->right);
        return leftSame && rightSame;
    }
};

Solution 2: #BFS

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que1;
        queue<TreeNode*> que2;
        que1.push(p);
        que2.push(q);
        while(!que1.empty() && !que2.empty()){
            auto node1 = que1.front();
            auto node2 = que2.front();
            que1.pop();
            que2.pop();
            if(node1 == nullptr || node2 == nullptr){
                if(node1 != node2) return false;
                continue;
            }
            if(node1->val != node2->val) return false;
            que1.push(node1->left);
            que1.push(node1->right);
            que2.push(node2->left);
            que2.push(node2->right);
        }
        return true;
    }
};

572. Subtree of Another Tree

Solution 1: #Recursion，这里比较难想的就是递归里面还嵌套了递归

class Solution {
private:
    bool isSame(TreeNode* l, TreeNode* r){
        if(l == nullptr && r == nullptr) return true;
        else if(l == nullptr || r == nullptr) return false;
        else if(l->val != r->val) return false;
        return isSame(l->left, r->left) && isSame(l->right, r->right);
    }
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root == nullptr) return false;
        if(subRoot == nullptr) return true;
        if(isSame(root, subRoot)) return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

Solution 2: #String， 思想就是前序遍历所有的节点用字符串存储起来

class Solution {
public:
    string serialize(TreeNode* node){
        if(!node) return "null";
        return "#" + to_string(node->val) + " " + serialize(node->left) + " " + serialize(node->right);
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        string rootStr = serialize(root);
        string subRootStr = serialize(subRoot);
        return rootStr.find(subRootStr) != string::npos;
    }
};

559. Maximum Depth of N-ary Tree

Solution 1: #Queue, #BFS

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) return 0;
        int height = 0;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            height++;
            while(n--){
                Node* cur = que.front();
                que.pop();
                for(auto c : cur->children) que.push(c);
            }
        }
        return height;
    }
};

Solution 2: #Recursion

class Solution {
public:
    int maxDepth(Node* root) {
        if(root == nullptr) return 0;
        int depth = 0;
        for(auto c : root->children){
            depth = max(depth, maxDepth(c));
        }
        return 1 + depth;
    }
};

222. Count Complete Tree Nodes

Solution 1: #Recursion，#DFS

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

Solution 2: #BFS, #Queue，用层序遍历扫一遍就行

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        int result = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            while(n--){
                TreeNode* cur = que.front();
                que.pop();
                result++;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

110. Balanced Binary Tree

Solution 1: #Recursion, #DFS

class Solution {
public:
     // get the height of the tree
    int height(TreeNode* root){
        if(root == nullptr) return 0;
        return 1 + max(height(root->left), height(root->right));
    }
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        if(abs(leftHeight - rightHeight) > 1) return false;
        // recursively check the subtree whether it is balanced or not
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

257. Binary Tree Paths

Solution 1: #DFS, #Recursion

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        dfs(root, "", ans);
        return ans;
    }
    void dfs(TreeNode* node, string path, vector<string>& ans){
        if(node == nullptr) return;
        path += to_string(node->val);
        if(!node->left && !node->right) ans.push_back(path);
        else{
            path += "->";
            dfs(node->left, path, ans);
            dfs(node->right, path, ans);
        }
    }
};

Solution 2: #Backtracking

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        backtracking(root, path, result);
        return result;
    }
    void backtracking(TreeNode* cur, string path, vector<string>& result){
        path += to_string(cur->val);
        if(cur->left == NULL && cur->right == NULL){
            result.push_back(path);
            return;
        }
        if(cur->left){
            path += "->";
            backtracking(cur->left, path, result);
            path.pop_back();
            path.pop_back();
        }
        if(cur->right){
            path += "->";
            backtracking(cur->right, path, result);
            path.pop_back();
            path.pop_back();
        }
    }
};

404. Sum of Left Leaves

Solution 1: #Recursion, #DFS

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;
        int leftValue = 0;
        if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) leftValue = root->left->val;
        return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

Solution 2: #BFS，#Queue, 直接用层序遍历扫一遍然后判断是否是叶子节点

class Solution {
public:
    // check the current node whether is leafnode or not
    bool isLeaf(TreeNode* node){
        if(node->left == nullptr && node->right == nullptr) return true;
        return false;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;    // edge case when root is NULL
        queue<TreeNode*> que;
        que.push(root);
        int leftSum = 0;
        while(!que.empty()){
            int n = que.size();
            while(n--){
                auto node = que.front();
                que.pop();
                if(node->left){
                    if(isLeaf(node->left)) leftSum += node->left->val;
                    que.push(node->left);
                }
                if(node->right) que.push(node->right);
            }          
        }
        return leftSum;

    }
};

513. Find Bottom Left Tree Value

Solution 1: #BFS, #Queue

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int left = 0;
        while(!que.empty()){
            left = que.front()->val;  // the leftmost node
            int n = que.size();
            while(n--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return left;
    }
};

Solution 2: #Recursion, #DFS

class Solution {
public:
    void dfs(TreeNode* root, int currDepth, int &maxDepth, int &ans){
        if(!root) return;
        if(currDepth > maxDepth){  // when reaching the next level
            ans = root->val;      // collect the leftmost node
            maxDepth = currDepth; // 是根据遍历顺序决定的
        }
        dfs(root->left, currDepth + 1, maxDepth, ans);
        dfs(root->right, currDepth + 1, maxDepth, ans);
    }
    int findBottomLeftValue(TreeNode* root) {
        if(!root->left && !root->right) return root->val;
        int ans = 0;
        int maxDepth = 0;
        dfs(root, 0, maxDepth, ans);
        return ans;
    }
};

112. Path Sum

Solution 1: #DFS, #Recursion

class Solution {
public:
    bool solve(TreeNode* root, int targetSum, int currSum){
        if(!root) return false;
        currSum += root->val;
        if(!root->left && !root->right && currSum == targetSum) return true;  
        bool leftAns = solve(root->left, targetSum, currSum);
        bool rightAns = solve(root->right, targetSum, currSum);
        return (leftAns || rightAns);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return solve(root, targetSum, 0);
    }
};

Solution 2: More optimistic recursion

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) return false;
        targetSum -= root->val;
        if(targetSum == 0 && !root->left && !root->right) return true;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

Solution 3: #BFS, #Queue, 给队列多开一个参数，记录当前的路径累加的和

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        queue<pair<TreeNode*, int>> que;
        que.push({root, root->val});
        while(!que.empty()){
            TreeNode* node = que.front().first;
            int currSum = que.front().second;
            que.pop();
            if(!node->left && !node->right && currSum == targetSum) return true;
            if(node->left) que.push({node->left, currSum + node->left->val});
            if(node->right) que.push({node->right, currSum + node->right->val});
        }
        return false;
    }
};

113. Path Sum II

Solution 1: # Backtracking

class Solution {
public:
    void solve(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& ans){
        if(root == NULL) return;
        path.push_back(root->val);
        if(root->left == NULL && root->right == NULL && root->val == targetSum){
            ans.push_back(path);
        }
        solve(root->left, targetSum - root->val, path, ans); 
        solve(root->right, targetSum - root->val, path, ans);
        path.pop_back();    // backtracking
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> ans;
        solve(root, targetSum, path, ans);
        return ans;
    }
};

Solution 2: # Backtracking, 更好的理解

class Solution {
public:
    void rec(TreeNode* root, int sum, int target, vector<int> path, vector<vector<int>>& ans){
        if(root == NULL) return;
        sum += root->val;
        path.push_back(root->val);
        // leafnodes that satisfy the target
        if(!root->left && !root->right && sum == target){ 
            ans.push_back(path);
            return;
        }
        rec(root->left, sum, target, path, ans);    // recursion
        rec(root->right, sum, target, path, ans);
        sum -= root->val;   // backtracking
        path.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> ans;
        rec(root, 0, targetSum, path, ans);
        return ans;
    }
};

106. Construct Binary Tree from Inorder and Postorder Traversal

Solution 1: #Recursion, 后序遍历的最后一个节点肯定是根节点，然后在中序遍历里面找到根节点的位置划分左右子树，再继续递归下去⚙️

class Solution {
public:
    TreeNode* rec(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd){
        if(inStart > inEnd) return nullptr;
        TreeNode* root = new TreeNode(postorder[postEnd]);
        int index = inStart;
        while(inorder[index] != root->val) index++;   // 找到中序遍历左右子树划分位置
        int leftLen = index - inStart;       // 左子树长度
        root->left = rec(inorder, postorder, inStart, index - 1, postStart, postStart + leftLen - 1);      // 递归
        root->right = rec(inorder, postorder, index + 1, inEnd, postStart + leftLen, postEnd - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return rec(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal

Solution 1: #Recursion， 和上一题一样，找到左右子树分割的下标，注意写递归一定要先写终止条件

class Solution {
public:
    TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart >= preEnd || inStart >= inEnd) {
            return nullptr; // 递归终止条件
        }    
        TreeNode* root = new TreeNode(preorder[preStart]);
        int idx = inStart;
        while (inorder[idx] != root->val) {
            idx++;
        }
        int leftLen = idx - inStart;   
        root->left = solve(preorder, inorder, preStart + 1, preStart + leftLen + 1, inStart, inStart + leftLen);
        root->right = solve(preorder, inorder, preStart + leftLen + 1, preEnd, inStart + leftLen + 1, inEnd);       
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return solve(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }
};

654. Maximum Binary Tree

Solution 1: # Recursion

class Solution {
public:
    int find(vector<int>& nums, int start, int end){    // 找到最大元素的下标
        int idx = start;
        for(int i = start; i <= end; i++){
            if(nums[i] > nums[idx]) idx = i;
        }
        return idx;
    }
    TreeNode* solve(vector<int>& nums, int start, int end){
        if(start > end) return nullptr;
        int idx = find(nums, start, end);
        TreeNode* root = new TreeNode(nums[idx]);
        root->left = solve(nums, start, idx - 1);
        root->right = solve(nums, idx + 1, end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

Solution 2 : #单调递减栈

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = nullptr;
        stack<TreeNode*> st;
        for(int num : nums){
            TreeNode* node = new TreeNode(num);
            while(!st.empty() && node->val > st.top()->val){
                node->left = st.top();
                st.pop();
            }
            if(!st.empty()){
                st.top()->right = node;
            }
            else{
                root = node;
            }
            st.push(node);
        }
        return root;
    }
};

617. Merge Two Binary Trees

Solution 1: #Recursion

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

Solution 2 : #Recursion, 上面版本更简略的递归写法

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

Solution 3: # Inorder Traversal, # Recursion

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

700. Search in a Binary Search Tree

Solution1: # Recursion

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root || root->val == val) return root;
        else if(val < root->val) return searchBST(root->left, val);
        else if(val > root->val) return searchBST(root->right, val);
        return nullptr;
    }
};

Solution 2: # Iterative

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root != nullptr){
            if(val < root->val) root = root->left;
            else if(val > root->val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

98. Validate Binary Search Tree

Solution 1: # Recursion

class Solution {
public:
    bool check(TreeNode* root, long long min, long long max){
        if(root == NULL) return true;
        if(root->val > min && root->val < max){
            bool left = check(root->left, min, root->val);
            bool right = check(root->right, root->val, max);
            return left && right;
        }
        return false;
    }
    bool isValidBST(TreeNode* root) {
        return check(root, LONG_MIN, LONG_MAX);
    }
};

Solution 2: # Iterative

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur != nullptr){       // collect all the left nodes
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top();
                st.pop();
                if(pre != NULL && cur->val <= pre->val) return false;
                pre = cur;
                cur = cur->right;
            }
        }
        return true;
    }
};

530. Minimum Absolute Difference in BST

Solution 1: # Inorder Traversal

class Solution {
public:
    void solve(TreeNode* root, vector<int>& ans){
        if(root == NULL) return;
        solve(root->left, ans);
        ans.push_back(root->val);
        solve(root->right, ans);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> ans;
        solve(root, ans);
        int result = INT_MAX;
        for(int i = 1; i < ans.size(); i++){
            result = min(result, ans[i] - ans[i - 1]);
        }
        return result;
    }
};

Solution 2: # Iterative

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        int result = INT_MAX;
        while(cur != NULL || !st.empty()){
            if(cur != NULL){
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top();
                st.pop();
                if(pre != NULL){
                    result = min(result, cur->val - pre->val);
                }
                pre = cur;
                cur = cur->right;
            }
        }
        return result;
    }
};

501. Find Mode in Binary Search Tree

Solution 1: #Hash Map, #Inorder Traversal

class Solution {
public:
    void collect(TreeNode* root, unordered_map<int, int>& mp){
        if(root == NULL) return;
        collect(root->left, mp);
        mp[root->val]++;
        collect(root->right, mp);
    }
    vector<int> findMode(TreeNode* root) {
        if(!root->left && !root->right) return {root->val};
        unordered_map<int, int> mp;
        vector<int> ans;
        collect(root, mp);
        int count = INT_MIN;  // the most frequency
        for(auto it : mp){
            if(it.second > count) count = it.second;
        }
        for(auto it : mp){
            if(it.second == count) ans.push_back(it.first);
        }
        return ans;
    }
};

236. Lowest Common Ancestor of a Binary Tree

Solution 1: # Recursion

class Solution {
public:
    bool exist(TreeNode* root, int value){
        if(root == NULL) return false;
        if(root->val == value) return true;
        bool left = exist(root->left, value);
        bool right = exist(root->right, value);
        return left || right;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val == p->val || root->val == q->val) return root;     // 打在根上
        else if(exist(root->left, p->val) && exist(root->right, q->val)) return root;  // 一边一个
        else if(exist(root->left, q->val) && exist(root->right, p->val)) return root;  // 一边一个
        else if(exist(root->left, p->val)) return lowestCommonAncestor(root->left, p, q);
        else return lowestCommonAncestor(root->right, p, q);
    }
};

Solution 2: #Recursion, 更精简的递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left == NULL) return right;
        if(right == NULL) return left;
        return root;
    }
};

235. Lowest Common Ancestor of a Binary Search Tree

Solution 1: #Recursion

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left == NULL) return right;
        if(right == NULL) return left;
        return root;
    }
};

Solution 2: #Iterative, 利用BST左低右高的性质，反复迭代🔁

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       while(root){
        if(root->val > p->val && root->val > q->val) root = root->left;
        else if(root->val < p->val && root->val < q->val) root = root->right;
        else return root;
       }
       return NULL;
    }
};

701. Insert into a Binary Search Tree

Solution 1: #Recursion

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

Solution 2: #Iterative

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL) return new TreeNode(val);
        TreeNode* cur = root;
        while(true){
            if(cur->val < val){
                if(cur->right) cur = cur->right;
                else{
                    cur->right = new TreeNode(val);
                    break;
                }
            }
            else{
                if(cur->left) cur = cur->left;
                else{
                    cur->left = new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }
};

450. Delete Node in a BST

Solution 1: #Recursion

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr) return root;
        if(key < root->val) root->left = deleteNode(root->left, key);
        else if(key > root->val) root->right = deleteNode(root->right, key);
        else{
            if(root->left == nullptr) return root->right;  // one child case
            else if(root->right == nullptr) return root->left;
            TreeNode* tmp = root->right; // to find min from subtree;
            while(tmp->left != nullptr) tmp = tmp = tmp->left;  // tmp has min
            root->val = tmp->val; // change root to min
            root->right = deleteNode(root->right, tmp->val); // delete old min
        }
        return root;
    }
};

669. Trim a Binary Search Tree

Solution 1: #Recursion

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == NULL) return NULL;
        if(root->val < low) return trimBST(root->right, low, high);
        if(root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

Solution 2: #Iterator

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return nullptr;
        // 修正头节点
        while(root && (root->val < low || root->val > high)){
            if(root->val < low) root = root->right;
            else root = root->left;
        }
        TreeNode* cur = root;
        // 修正左子树
        while(cur){
            while(cur->left && cur->left->val < low){
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;
        // 修正右子树
        while(cur){
            while(cur->right && cur->right->val > high){
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

108. Convert Sorted Array to Binary Search Tree

Solution 1: #Recursion

class Solution {
public:
    TreeNode* solve(vector<int>& nums, int start, int end){
        if(start > end) return nullptr;
        int mid = (start + end) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = solve(nums, start, mid - 1);
        root->right = solve(nums, mid + 1, end);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

538. Convert BST to Greater Tree

Solution 1: #Recursion

class Solution {
private:
    int pre = 0;  //记录遍历的前一个节点的值
    void traversal(TreeNode* cur){
        if(cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

Solution 2: #Stack

class Solution {
public:
    void dfsIn(TreeNode* root, stack<TreeNode*> &st){
        if(root == NULL) return;
        dfsIn(root->left, st);
        st.push(root);
        dfsIn(root->right, st);
    }
    TreeNode* convertBST(TreeNode* root) {
        stack<TreeNode*> st;
        dfsIn(root, st);
        int sum = 0;
        while(!st.empty()){
            TreeNode* p = st.top();
            st.pop();
            sum += p->val;
            p->val = sum;
        }
        return root;
    }
};
滚动至顶部