首页 编程 Leetcode

# 一、理论基础

要了解二叉树的几种类型 / 定义；

要熟悉几种遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

见 [[二叉树_0.png]]、[[二叉树_1.png]]

# 1.1 递归法

# i、递归法前序遍历：

1
2
3
4
5
6
void preorderTraversal(TreeNode* cur, vector<int>& vec) {
    if(cur == nullptr) return;
    vec.push_back(cur->val);
    traversal(cur->left, vec);
    traversal(cur->right, vec);
}

# i、递归法中序遍历：

1
2
3
4
5
6
void inorderTraversal(TreeNode* cur, vector<int>& vec) {
    if(cur == nullptr) return;
    traversal(cur->left, vec);
    vec.push_back(cur->val);
    traversal(cur->right, vec);
}

# i、递归法后序遍历：

1
2
3
4
5
6
void postorderTraversal(TreeNode* cur, vector<int>& vec) {
    if(cur == nullptr) return;
    traversal(cur->left, vec);
    traversal(cur->right, vec);
    vec.push_back(cur->val);
}

# 1.2 迭代法

# i、迭代法前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    stack<TreeNode*> st;
    if(root != nullptr) st.push(root);

    while(!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if(cur->right) st.push(cur->right);
        if(cur->left) st.push(cur->left);
    } return ret;
}

前序遍历顺序是 “中左右”，但是由于栈的性质是先进后出，所以这里 push 时要变成 “右左” 的顺序。（这样的话，pop 的时候才能先左后右。注意这里，我们的左右是相对于 stack 而言的，而 cur-val 是 push 进 vector 里面的。）

# i、迭代法中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while(cur != nullptr || !st.empty()) {
        if(cur != nullptr) { // 指针来访问节点，访问到最底层
            st.push(cur); // 将访问的节点放进栈
            cur = cur->left;  // 左
        } else {
            cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
            st.pop();
            result.push_back(cur->val); // 中
            cur = cur->right;  //右
        }
    } return result;
}

注意这里，迭代法对于中序遍历的写法在框架上和前序 / 后序有所差异，并不是简单调换节点入栈顺序就可以的。
这是因为，前序遍历的顺序是 “中左右”，先访问的元素是中间节点，要处理的元素也是中间节点，所以才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

# i、迭代法后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    stack<TreeNode*> st;
    if(root != nullptr) st.push(root);

    while(!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if(cur->left) st.push(cur->left);
        if(cur->right) st.push(cur->right);
    } reverse(ret.begin(), ret.end());
    return ret;
}

这里还得 reverse 翻转一下，hmmm...
后序遍历的顺序是 “左右中”，我们这里先是 “中左右”，经过 stack 的性质，变成了 “中右左”，最后我们再整体对 vector 进行翻转，成为 “左右中”。

# 1.3 统一版迭代法

如果想要把迭代法的三种遍历顺序都统一成一种形式，则有：

# i、迭代法统一版前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root != nullptr) st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if(node != nullptr) {
                if(node->right) st.push(node->right);  // 右
                if(node->left) st.push(node->left);    // 左
                st.push(node);                         // 中
                st.push(nullptr);
            } else {
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        } return result;
    }
};

在这里，向栈中压入 nullptr 的目的是为了标记前一个元素已经被访问过，需要将其压入的 vector 中了。

具体地，下面是一个简化的流程，帮助理解 nullptr 的作用：

  • 假设有一个节点结构如下：

    1
    2
    3
      A
     / \
    B   C

  • 遍历开始时，将 A 压入栈，然后进入循环。

  • 当处理 A 时，将 C（右子树）和 B（左子树）压入栈，接着压入 A 本身和 nullptr ：

    • 栈内容： [C, B, A, nullptr]

  • 处理 A，弹出 A 并检查：

    • 弹出 nullptr ，然后弹出 A，添加 A 的值到结果。

  • 现在处理 B：

    • 将 B 压入栈时，栈会包含： [C, B, nullptr]
    • 处理 B，添加 B 的值到结果，然后处理其子节点（如果有）。

这里，由于我们前序遍历的顺序是 “中左右”，根据栈的先进先出的特性，我们需要以 “右左中” 的顺序入栈。
而如果以此顺序入栈，那么栈顶元素为 “中”，如果再对其进行 “右左中” 处理，则无限循环了。此时我们不应该对其进行进一步地访问，而是应该将其值进行存储了。所以 nullptr 的作用就是为了标记它的这种状态。

# i、迭代法统一版中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root != nullptr) st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if(node != nullptr) {
                if(node->right) st.push(node->right);  // 右
                st.push(node);                         // 中
                st.push(nullptr);
                if(node->left) st.push(node->left);    // 左
            } else {
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        } return result;
    }
};

这里要注意，我们的 nullptr 是用来标记 “中” 节点的，所以要跟着 node 一起移动顺序。下面的后序遍历同理。

# i、迭代法统一版后序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root != nullptr) st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if(node != nullptr) {
                st.push(node);                         // 中
                st.push(nullptr);
                if(node->right) st.push(node->right);  // 右
                if(node->left) st.push(node->left);    // 左
            } else {
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        } return result;
    }
};

# 2.0 层序遍历

维护一个队列，利用其先进先出的特性，访问当前层的数据，同时，将下一层的数据压入到队列尾端，等待下一次遍历。
那么，每次循环需要通过获取队列长度来判断每层循环的次数（因为我们在遍历当前层时还会不断将下一层的数据入栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    queue<TreeNode*> que;
    if(root) que.push(root);
    while(!que.empty()) {
        vector<int> layer;
        int layer_size = que.size();
        for(int i = 0; i < layer_size; ++i) {  // 这里要使用固定的size，不能在这里输入 que.size()，因为它实时变化
            TreeNode* node = que.front();
            que.pop();
            layer.push_back(node->val);
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        } ret.push_back(layer);
    } return ret;
}

# 3.0 其他

# i、满二叉树

对于深度为 (n) 的满二叉树，节点的总数可以用以下公式计算：

N=2n+1−1N = 2^{n+1} - 1

其中，

  • 深度 (n) 指的是从根节点到最深叶子节点的最长路径上的边的数量。
  • 满二叉树 是一种每个节点都有两个子节点的二叉树，除了最深层的叶子节点外，所有层的节点数都达到了最大。

则有：

  • 当 n = 0（树的深度为 0），节点总数为 20+1−1=12^{0+1} - 1 = 1。
  • 当 n = 1（树的深度为 1），节点总数为 21+1−1=32^{1+1} - 1 = 3。
  • 当 n = 2（树的深度为 2），节点总数为 22+1−1=72^{2+1} - 1 = 7。

在实际计算中，我们可以用移位操作代替指数运算，则有 N = (2 << n) - 1

# 二、题目实践

# 1、144. 二叉树的前序遍历

见上文理论基础部分；

# 2、94. 二叉树的中序遍历

见上文理论基础部分；

# 3、145. 二叉树的后序遍历

见上文理论基础部分；

# 4、102. 二叉树的层序遍历

见上文理论基础部分；

# 5、226. 翻转二叉树

  1. 思路 1：
    递归法，一想就会，一写就对，没啥难度：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(!root) return root;
            swap(root->left, root->right);
            invertTree(root->left);
            invertTree(root->right);
            return root;
        }
    };

  2. 思路 2：
    层序遍历。逐层逐个遍历节点，对每个节点的左右子节点进行翻转。
    这里需要注意的是，我们并不需要记录每一层的元素的数量，因为我们不 care：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            queue<TreeNode*> que;
            if(root) que.push(root);
            while(!que.empty()) {
                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;
        }
    };

# 6、101. 对称二叉树

一上来想到的思路是层序遍历，把每一层的元素压入一个 vector，然后判断这个 vector 是否对称：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool isVectorSymmetric(vector<TreeNode*>& vec) {
        for(int i = 0, j = vec.size() - 1; i < j; ++i, --j) {
            if(vec[i] && vec[j] && vec[i]->val != vec[j]->val) {
                return false;
            }

            if((!vec[i] && vec[j]) || (vec[i] && !vec[j])) {
                return false;
            }
        } return true;
    }

    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()) {
            int layer_size = que.size();
            vector<TreeNode*> layer;
            for(int i = 0; i < layer_size; ++i) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                layer.push_back(node->left);
                layer.push_back(node->right);
            }

            if(!isVectorSymmetric(layer)) {
                return false;
            }
        } return true;
    }
};

  1. 思路 2：
    在层序遍历的基础之上，其实我们不需要每次把一整层的元素拿来遍历判断是否对称。
    我们利用 “递归” 思想，只需要判断当前左右两个节点是否相等即可，然后在把当前两个节点的子节点压入队列进行下一轮比较，在入队时，“左左” 对应 “右右”，“左右” 对应 “右左”。其实算是迭代法，不能算是层序遍历了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
            if(root == nullptr) return true;
            queue<TreeNode*> que;
            que.push(root->left);
            que.push(root->right);

            while(!que.empty()) {
                TreeNode* left = que.front(); que.pop();
                TreeNode* right = que.front(); que.pop();
                if(!left && !right) {  // 左右皆空，此时说明是对称的
                    continue;
                }

                // 左右一个节点不为空，或者都不为空但数值不相同，返回false
                if((!left || !right || (left->val != right->val))) {
                    return false;
                }

                que.push(left->left);
                que.push(right->right);
                que.push(left->right);
                que.push(right->left);
            } return true;
        }
    };

  2. 思路 3：
    那么，既然思路 3 说是递归思想了，那我们自然而然可以用递归法来做这道题：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
        bool compare(TreeNode* left, TreeNode* right) {
            if(!left && !right) {  // 左右皆空，此时说明是对称的
                return true;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if((!left || !right || (left->val != right->val))) {
                return false;
            }

            bool outside = compare(left->left, right->right);
            bool inside = compare(left->right, right->left);
            return (outside && inside);
        }

        bool isSymmetric(TreeNode* root) {
            if(root == nullptr) return true;
            return compare(root->left, root->right);
        }
    };

# 7、104. 二叉树的最大深度

  1. 思路 1：
    这道题一上来我的第一反应还是层序遍历（真好用嘿嘿嘿），逐层遍历，但是不 care 每一层有什么元素，每遍历一层，深度加一，最后返回深度即可：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            int depth = 0;
            queue<TreeNode*> que;
            if(root) que.push(root);
            while(!que.empty()) {
                int layer_size = que.size();
                for(int i = 0; i < layer_size; ++i) {
                    TreeNode* node = que.front(); que.pop();
                    if(node->left) que.push(node->left);
                    if(node->right) que.push(node->right);
                } ++depth;
            } return depth;
        }
    };

  2. 思路 2：
    另一种思路就是递归，当前节点的最大深度等于左右子节点的最大深度 + 1：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        int getdepth(TreeNode* node) {
            if(node == nullptr) return 0;
            int leftdepth = getdepth(node->left);       // 左
            int rightdepth = getdepth(node->right);     // 右
            int depth = 1 + max(leftdepth, rightdepth); // 中
            return depth;
        }

        int maxDepth(TreeNode* root) {
            return getdepth(root);
        }
    };

# 8、559. N 叉树的最大深度

在上一题的基础之上来做这道题，就很简单了：

  1. 思路 1：
    还是层序遍历，和上一题的唯一区别就是我们在处理节点的子节点时，需要遍历 children 里面的所有子节点：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int maxDepth(Node* root) {
            int depth = 0;
            queue<Node*> que;
            if(root) que.push(root);
            while(!que.empty()) {
                int layer_size = que.size();
                for(int i = 0; i < layer_size; ++i) {
                    Node* node = que.front(); que.pop();
                    for(Node* child : node->children) {
                        if(child) que.push(child);
                    }
                } ++depth;
            } return depth;
        }
    };

  2. 思路 2：
    递归。这里其实思路和上一题一致，只不过这里简化了递归的写法，合并在同一个函数，看上去可能有点抽象：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        int maxDepth(Node* root) {
            if(root == 0) return 0;
            int depth = 0;
            for(int i = 0; i < root->children.size(); ++i) {
                depth = max(depth, maxDepth(root->children[i]));
            } return depth + 1;
        }
    };

# 9、111. 二叉树的最小深度

这题我倒是不会。

  1. 思路 1：
    层序遍历，（我怎么没想到），对于每层元素，一旦存在叶子节点，则找到最小深度，立即返回当前深度即可：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(root == nullptr) return 0;
            int depth = 0;
            queue<TreeNode*> que;
            que.push(root);
            while(!que.empty()) {
                int size = que.size();
                depth++;
                for(int i = 0; i < size; ++i) {
                    TreeNode* pNode = que.front();
                    que.pop();
                    if(pNode->left) que.push(pNode->left);
                    if(pNode->right) que.push(pNode->right);
                    if(!pNode->left && !pNode->right) {
                        return depth;
                    }
                }
            } return depth;
        }
    };

  2. 思路 2：
    递归。这里相较于求最大深度的那道题来说，略有不同。
    当前节点的最小深度，并非单纯的是 1 + min(lhs, rhs) 这么简单，因为这样我们会把一些不符题意的节点算进来。
    注意看题，我们要找到的是叶子节点，也就是左右两个子节点都为空。
    但 1 + min(lhs, rhs) 会把 “左节点为空，右节点非空” or “左节点非空，右节点为空” 给算进来。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(root == nullptr) return 0;
            int lhs = minDepth(root->left);
            int rhs = minDepth(root->right);

            if(root->left == nullptr && root->right != nullptr) {
                return 1 + rhs;
            } else if (root->left != nullptr && root->right == nullptr) {
                return 1 + lhs;
            }

            return 1 + min(lhs, rhs);
        }
    };

# 10、222. 完全二叉树的节点个数

  1. 思路 1：
    一上来想到的当然就是我最爱的层序遍历了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int countNodes(TreeNode* root) {
            int cnt = 0;
            queue<TreeNode*> que;
            if(root) que.push(root);
            while(!que.empty()) {
                int layer_size = que.size();
                for(int i = 0; i < layer_size; ++i) {
                    TreeNode* node = que.front(); que.pop();
                    if(node->left) que.push(node->left);
                    if(node->right) que.push(node->right);
                    ++cnt;
                }
            } return cnt;
        }
    };

    但是题目既然给了 “完全二叉树” 这个条件，肯定有用，但是这里如果我们用层序遍历的话，没利用上这个条件。

  2. 思路 2：
    递归。

这里的思路是，分别求左右子树的深度，如果左右子树的深度相等，这说明该树为满二叉树，那么根据公式可求得节点数量；如果左右子树深度不相等，则递归分别求左右子树的数量，当前子树的总节点数等于 1 + 左节点子树节点数 + 右节点子树节点数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;

        TreeNode* pLeft = root->left, *pRight = root->right;
        int leftDepth = 0, rightDepth = 0;

        while(pLeft) {
            pLeft = pLeft->left;
            leftDepth++;
        }

        while(pRight) {
            pRight = pRight->right;
            rightDepth++;
        }

        if(leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        } else {
            return 1 + countNodes(root->left) + countNodes(root->right);
        }
    }
};

# 11、110. 平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

  1. 思路 1：
    这题我没想出来 😦

思路就是，递归求左右子节点的高度，判断其差值是否大于 / 小于 1。
同时，在求子节点的高度是，如果子树已经是一个非平衡二叉树了，直接返回 -1，用于标记。否则返回子树的高度；
对于当前节点，判断左右子树的高度差是否大于一，大于则非平衡，同样地，返回 -1 用于标记。否则，返回 1 + 左右子树的高度的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int getHeight(TreeNode* root) {
        if(!root) return 0;
        int lhs_height = getHeight(root->left);
        if(lhs_height == -1) return -1;
        int rhs_height = getHeight(root->right);
        if(rhs_height == -1) return -1;
        
        if(abs(lhs_height - rhs_height) > 1) {
            return -1;
        } else {
            return 1 + max(lhs_height, rhs_height);
        }
    }

    bool isBalanced(TreeNode* root) {
        return (getHeight(root) == -1 ? false : true);
    }
};

# 12、257. 二叉树的所有路径

#回溯

  1. 思路 1：
    这里采用了递归和回溯的思想，从当前节点开始向下递归遍历，如果遇到叶子节点，则视为找到答案，保存答案，同时，返回上一节点，即回溯，找寻下一个可能的节点。

具体地，维护一个 result 用于存储最终的答案，用于一个 path 用于存储当前走过的路径。每遍历一个节点，把当前节点压入 path，直到叶子节点，则视为找到答案，遍历 path 构造答案压入 result 中。每执行完一次递归，（即调用 traversal ）回来之后要 pop，以模拟回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private:
    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val);
        if(!cur->left && !cur->right) {
            string sPath;
            for(int i = 0; i < path.size(); i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            } sPath[sPath.size()-2] = '\0';  // 去除多余的 "->"
            result.push_back(sPath);
            return;
        }
        if(cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
        if(cur->left) { // 左
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(!root) return result;
        traversal(root, path, result);
        return result;
    }
};

这里左子节点和右子节点的遍历顺序无所谓，可颠倒，所以我刻意写的先右后左的顺序。

对于上述代码，在思路不变的情况下，可以优化成以下形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val);  // 当前节点
        if(!cur->left && !cur->right) {
            result.push_back(path);
            return;
        }
        if(cur->right) traversal(cur->right, path + "->", result); // 右
        if(cur->left) traversal(cur->left, path + "->", result); // 左
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if(!root) return result;
        traversal(root, path, result);
        return result;
    }
};

之前，我们每找到一个结果，要重新遍历整个 path 数组来构造答案，我们其实可以直接传递字符串，在传递过程中不断增加 / 删除节点。这样，我们把递归函数传参中的 path 改为值传递，每次调用时加上 “->”，在递归函数中在加上值 "cur-val"，而由于是值传递，递归返回时则自动回溯，不需要 pop 操作。

  1. 思路 2：
    迭代法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> treeSt;  // 保存树的遍历节点
        stack<string> pathSt;  // 保存遍历路径的节点
        vector<string> result;  // 保存最终路径集合
        if(!root) return result;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while(!treeSt.empty()) {
            // 当前节点
            TreeNode* node = treeSt.top(); treeSt.pop();
            string path = pathSt.top(); pathSt.pop();
            if(!node->left && !node->right) {
                result.push_back(path);
            }
            if(node->left) { // 左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));  // 注意在这里隐含了回溯
            }
            if(node->right) { // 右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));  // 注意在这里隐含了回溯
            }
        } return result;
    }
};

# 13、404. 左叶子之和

  1. 思路 1：
    递归，逐步拆解问题成更小规模的子问题。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        int leftleaves(TreeNode* root, bool isLeft) {
            if(!root) return 0;
            if(!root->left && !root->right && isLeft) {
                return root->val;
            } else {
                return leftleaves(root->left, true) + leftleaves(root->right, false);
            }
        }

        int sumOfLeftLeaves(TreeNode* root) {
            return root ? leftleaves(root->left, true) + leftleaves(root->right, false) : 0;
        }
    };

    这里我们需要有一个额外的标志来判断当前节点是否为左边的节点，需要靠父节点来判断，即从父节点调用前就明确。

  2. 思路 2：
    有递归，自然就有迭代法，同理，我们这里入栈时多压入一个标志位，每次 pop 的时候同时 pop 标志位，用以判断：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    public:
        int sumOfLeftLeaves(TreeNode* root) {
            if(root == nullptr) { return 0; }
            int result = 0;
            stack<TreeNode*> st;
            TreeNode* LEFT = new TreeNode(-1);
            TreeNode* RIGHT = new TreeNode(-1);
            st.push(root); st.push(RIGHT);
            while(!st.empty()) {
                TreeNode* pSide = st.top(); st.pop();
                TreeNode* pNode = st.top(); st.pop();

                if(pSide == LEFT && !pNode->left && !pNode->right) {
                    result += pNode->val;
                }

                if(pNode->left) {
                    st.push(pNode->left); st.push(LEFT);
                }

                if(pNode->right) {
                    st.push(pNode->right); st.push(RIGHT);
                }
            } delete LEFT, delete RIGHT;
            return result;
        }
    };

# 14、513. 找树左下角的值

  1. 思路 1：
    最先想到的就是我最爱的层序遍历，每一层一开始先记录最左边的元素，逐层更新：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            int ret = -1;
            queue<TreeNode*> que;
            que.push(root);
            while(!que.empty()) {
                int layer_size = que.size();
                for(int i = 0; i < layer_size; ++i) {
                    TreeNode* node = que.front(); que.pop();
                    if(i == 0) ret = node->val;
                    if(node->left) que.push(node->left);
                    if(node->right) que.push(node->right);
                }
            } return ret;
        }
    };

  2. 思路 2：
    递归，维护一个深度值，当遇到叶子节点时如果深度大于当前记录的最大深度值，则更新。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        int result;
        int maxDepth = INT_MIN;
        void traversal(TreeNode* root, int depth) {
            if(!root->left && !root->right) {
                if(depth > maxDepth) {
                    maxDepth = depth;
                    result = root->val;
                }
                return;
            }
            if(root->left) {
                traversal(root->left, depth + 1);  // 隐含回溯
            }
            if(root->right) {
                traversal(root->right, depth + 1);  // 隐含回溯
            }
            return;
        }

        int findBottomLeftValue(TreeNode* root) {
            traversal(root, 0);
            return result;
        }
    };

    这里先遍历左子树，再遍历右子树。在这段代码中，左子树会在右子树之前被处理，因此在最底层的情况下，左子节点会先被记录。由于左子节点会优先被遍历并记录，只有在左子节点没有更新时，才会记录右子节点的值。这保证了在同一深度下，最先遇到的叶子节点是左节点，从而实现了寻找最底层的最左侧节点的目标。

# 15、112. 路径总和

#回溯

  1. 思路 1：
    二叉树的题目，除了那些一上来明显能想到思路的，否则基本上就是先思考递归写法，然后再考虑把递归写法优化成迭代写法。这里我们用递归写法，判断当前是否存在路径，等价于求两个子树是否存在路径，只需要其中一个存在即可，所以是 “或” 的关系。每次递归时，把 targetSum 减去当前节点的值，则我们只需要在叶子节点判断 targetSum 是否等于叶子节点的 val 即可。这里的回溯隐含在函数传参 targetSum 中。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        bool isPathSumExist(TreeNode* root, int targetSum) {
            if(!root) return false;
            if(!root->left && !root->right) {
                return root->val == targetSum;
            } else {
                return isPathSumExist(root->left, targetSum - root->val) || isPathSumExist(root->right, targetSum - root->val);
            }
        }

        bool hasPathSum(TreeNode* root, int targetSum) {
            return isPathSumExist(root, targetSum);
        }
    };

  2. 思路 2：

第二种思路是迭代，这种思路的关键是怎么处理 targetSum 以及怎么回溯。
这里的做法是，在栈中压入的是一个 pair，同时记录当前节点和到当前位置的路径和。
则在叶子节点时只需要判断当前位置的路径和是否等于 targetSum 即可，压入普通子节点时则是通过将当前节点的 val 与 sum 求和压入，这里就实现了隐含的回溯。（因为我们的 sum 是维护在过程中的，是暂存在每一个节点的，每一次访问栈中元素 pop 时就回溯了。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        stack<std::pair<TreeNode*, int>> st;
        st.push(pair<TreeNode*, int>(root, root->val));

        while(!st.empty()) {
            auto [node, sum] = st.top(); st.pop();
            if(!node->left && !node->right && sum == targetSum) {
                return true;
            }
            if(node->left) {
                st.push(pair<TreeNode*, int>(node->left, sum + node->left->val));
            }
            if(node->right) {
                st.push(pair<TreeNode*, int>(node->right, sum + node->right->val));
            }
        } return false;
    }
};

# 16、106. 从中序与后序遍历序列构造二叉树

  1. 思路 1：

首先有个基础的知识点，即如何利用中序遍历和后序遍历来确定一个二叉树：
我们知道后序遍历的顺序是 “左右中”，所以 postorder 数组中的最后一个元素一定是中间节点。
其次，我们知道中序遍历的顺序是 “左中右”，所以我们可以利用上面得到的中间节点，在 inorder 数组中找到中间节点的位置，然后把中序遍历数组的左边和右边分出来。
最后，我们再根据 “中序遍历和后序遍历的长度应该一致”，可以利用中序遍历分割的子数组长度，来确认如何分割后续遍历的数组。

于是这题的思路就是，递归，每一次利用后序遍历的最后一个元素来定位中间节点在中序遍历中的位置，然后将数组一分为二（实际上是一分为三：当前节点 —— 即中间节点、左子树、右子树），再利用得到的数组长度反过来去分割后序遍历，同样得到左子树和右子树（至于结尾的中间节点，我们直接 pop 掉，因为我们在处理中序遍历的时候已经生成了中间节点了，不需要重复累赘操作）

而这里如何递归也是一个关键点。首先，我们每次迭代都能得到一个中间节点，该节点的值就是后序遍历的尾端元素。而其左右子树，我们则通过递归左右子树的子数组来得到。所以，递归终止的条件，就是后序遍历的数组长度为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    int getSplitVectorIdx(vector<int>& input, int val) {
        for(int i = 0; i < input.size(); ++i) {
            if(input[i] == val) {
                return i;
            }
        } return -1;
    }

public:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.empty()) return nullptr;

        int mid_val = postorder[postorder.size() - 1];
        TreeNode* node = new TreeNode(mid_val);

        if(postorder.size() == 1) {
            return node;
        }

        int mid_idx = getSplitVectorIdx(inorder, mid_val);
        vector<int> left_inorder(inorder.begin(), inorder.begin() + mid_idx);
        vector<int> right_inorder(inorder.begin() + mid_idx + 1, inorder.end());

        postorder.pop_back();
        vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
        vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end());

        node->left = traversal(left_inorder, left_postorder);
        node->right = traversal(right_inorder, right_postorder);
        return node;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()) return nullptr;
        return traversal(inorder, postorder);
    }
};

这里有一个优化点，就是每一次迭代都要去 “分割数组”，而我们这里的 “分割” 是通过生成数组来实现的，会有消耗。
我们完全可以只记录 inorder 和 postorder 两个数组的头尾 index 即可。然后在具体的迭代中，我们再根据两个 index 求得 4 个 index。这里就不展开了。

另外，还要注意，题目里给定了一个条件，就是两个遍历的数组里面不包含相同元素，这一点很重要。不然我们没法定位。

最后，
前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
前序和后续不可以唯一确定一棵二叉树。

# 17、654. 最大二叉树

  1. 思路 1：

有了上一题的 “经验教训”，我们这一题基本就知道怎么通过递归来实现了。
这题有更强的递归模拟性，也跟上一题一样是划分数组，所以这一次我们直接通过传递数组范围的方式，避免了数组的创建和拷贝。对于范围，我们始终以左闭右开区间为准。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
private:
    int findMaxVal(vector<int>& nums, int start, int end) {
        int ret = -1;
        int max = -1;
        for(int i = start; i < end; ++i) {
            if(nums[i] > max) {
                max = nums[i];
                ret = i;
            }
        } return ret;
    }

    TreeNode* traversal(vector<int>& nums, int start, int end) {  // [start, end)
        if(start >= end) {
            return nullptr;
        }

        int idx = findMaxVal(nums, start, end);
        TreeNode* node = new TreeNode(nums[idx]);

        node->left = traversal(nums, start, idx);
        node->right = traversal(nums, idx + 1, end);
        return node;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.empty()) return nullptr;
        return traversal(nums, 0, nums.size());
    }
};

这里要注意一个小细节就是，如果我们要以数组的范围作为参数传递，则递归终止的条件不能以数组是否为空来判断，而是应该判断 start 是否大于等于 end。

# 18、617. 合并二叉树

  1. 思路 1：
    递归模拟，现在基本有经验了，递归函数中处理的是【当前节点】，同时，当前节点的左右两个子节点通过调用递归函数交给下一轮递归来得到。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    private:
        TreeNode* merge(TreeNode* root1, TreeNode* root2) {
            if(!root1 && !root2) return nullptr;
            if(!root1 && root2) return root2;
            if(root1 && !root2) return root1;

            TreeNode* node = new TreeNode(root1->val + root2->val);
            node->left = merge(root1->left, root2->left);
            node->right = merge(root1->right, root2->right);
            return node;
        }

    public:
        TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
            if(!root1 && !root2) return nullptr;
            return merge(root1, root2);
        }
    };

当然，这上面的这个解法由于是我 “简单应付” 的，所以效率不高，还申请了新的内存，有优化空间。优化后可得：

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
};

  1. 思路 2：
    有递归的地方基本就有迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) { return root2; }
        if(root2 == nullptr) { return root1; }
        
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);

        while(!que.empty()) {
            TreeNode* pNode1 = que.front(); que.pop();
            TreeNode* pNode2 = que.front(); que.pop();

            pNode1->val += pNode2->val;

            if(pNode1->left && pNode2->left) {
                que.push(pNode1->left);
                que.push(pNode2->left);
            }

            if(pNode1->right && pNode2->right) {
                que.push(pNode1->right);
                que.push(pNode2->right);
            }

            if(!pNode1->left && pNode2->left) {
                pNode1->left = pNode2->left;
            }

            if(!pNode1->right && pNode2->right) {
                pNode1->right = pNode2->right;
            }
        } return root1;
    }
};

这里需要注意的是，虽然我们每一轮循环处理的是当前节点，但是我们只需要把两个值（如果存在）相加即可，并不需要通过 “父节点” 来做这件事。同时，这里如果 pNode1->xxx && !pNode2->xxx 的情况没有写出相应的逻辑，因为不用处理。

# 19、700. 二叉搜索树中的搜索

二叉搜索树的特性是，左子树节点的值均小于根节点的值，右子树节点的值均大于根节点的值。
二叉搜索树的中序遍历得到的是一个有序的数列。

  1. 思路 1：
    直接迭代，类似于处理链表：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        TreeNode* searchBST(TreeNode* root, int val) {
            TreeNode* ret = nullptr;
            while(root) {
                if(root->val == val) {
                    ret = root;
                    break;
                } else if (root->val > val) {
                    if(root->left) {
                        root = root->left;
                    } else {
                        break;
                    }
                } else if (root->val < val) {
                    if(root->right) {
                        root = root->right;
                    } else {
                        break;
                    }
                }
            } return ret;
        }
    };

我上面写得太累赘了，可以优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root) {
            if(root->val > val) {
                root = root->left;
            } else if(root->val < val) {
                root = root->right;
            } else {
                return root;
            }
        } return nullptr;
    }
};

  1. 思路 2：
    递归，但我怀疑正常人第一反应真的会想到这个吗...
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution {
    public:
        TreeNode* searchBST(TreeNode* root, int val) {
            if(!root || root->val == val) { return root; }
            if(root->val > val) { return searchBST(root->left, val); }
            if(root->val < val) { return searchBST(root->right, val); }
            return nullptr;
        }
    };

# 20、98. 验证二叉搜索树

这里我写了两种错误的做法。注意，以下两个写法无法通过全部测试用例！！

1
2
3
4
5
6
7
8
9
10
11
12
13
// class Solution {
// public:
// 	bool isValidBST(TreeNode* root) {
// 		if(!root) return true;
// 		if(root->left && root->left->val >= root->val) {
// 			return false;
// 		}
// 		if(root->right && root->right->val <= root->val) {
// 			return false;
// 		}
// 		return isValidBST(root->left) && isValidBST(root->right);
// 	}
// };

在我的第一版写法中，我企图通过一个简单的递归来解题。但是遇到了这样的测试用例：
1
2
3
4
5
  5
 / \
4    6
    / \
   3   7

于是我写了第二版，要解决子节点和祖节点的大小问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// class Solution {
// private:
// 	bool traversal(TreeNode* root, TreeNode* last, int dir) {
// 		if(!root) return true;
// 		if(root->left && root->left->val >= root->val) {
// 			return false;
// 		}
// 		if(root->right && root->right->val <= root->val) {
// 			return false;
// 		}
// 		if(last && dir == 0 && root->right && root->right->val >= last->val) {
// 			return false;
// 		}
// 		if(last && dir == 1 && root->left && root->left->val <= last->val) {
// 			return false;
// 		}

// 		return traversal(root->left, root, 0) && traversal(root->right, root, 1);
// 	}

// public:
// 	bool isValidBST(TreeNode* root) {
// 		return traversal(root, nullptr, 0);
// 	}
// };

通过了 95% 的测试用例，但是在这个测试用例卡住了：

1
2
3
4
5
6
7
            120
         /        \
       70            140
     /   \           /   \
   50    100        130    160
  / \    / \        / \     / \
20  55  75  110   119 135  150 200

那么，正解是什么呢？
注意，我们要判断它是不是二叉搜索树，那么，我们只要判断它是否具有二叉搜索树的特性即可！
而二叉搜索树有什么特性呢？—— 中序遍历的结果是单调递增的！
那么这道题就变成一道简单的 “中序遍历”+“判断数组是否单调递增” 了。

  1. 思路 1：
    思路如上所述。
    这里采用中序遍历的迭代写法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            vector<int> result;
            stack<TreeNode*> st;
            TreeNode* cur = root;
            while(cur || !st.empty()) {
                if(cur) {
                    st.push(cur);
                    cur = cur->left;  // 左
                } else {
                    cur = st.top(); st.pop();
                    result.push_back(cur->val); // 中
                    cur = cur->right;  //右
                }
            }
            
            for(int i = 1; i < result.size(); ++i) {
                if(result[i-1] >= result[i]) {
                    return false;
                }
            } return true;
        }
    };

    这里中序的迭代写法需要理解，一路无脑向左遍历直到不再有左子节点，（则当前节点就是左节点），压入当前节点。如果当前节点没有右子节点，则回到上一个节点（即中节点），压入中节点，再遍历右节点。左、中、右，中序遍历。

  2. 思路 2：
    有迭代的地方就有递归。这里同样的思路，用递归法实现中序遍历，同样能够解题：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        long long maxVal = LONG_MIN;
        bool isValidBST(TreeNode* root) {
            if(!root) return true;

            bool left = isValidBST(root->left);
            if(maxVal < root->val) {
                maxVal = root->val;
            } else {
                return false;
            }
            bool right = isValidBST(root->right);

            return left && right;
        }
    };

    这里维护一个 “最大值”，该值可代表遍历左子树时遇到的最大值。则有，如果该值大于当前 root->val 值，说明不合题意，返回 false，其余情况下更新该值。由于 maxVal 表示左子树的最大值，且当处理当前节点时，我们会将其与当前节点的值进行对比并更新，所以当我们开始遍历右子树时，该值 maxVal 已然是根节点的值，所以此时如果我们的右子树的左端出现比该值小的情况，会被判为 false。也就剔除了上面的 120 > 119 的测试用例的情况。

而这种解法的弊端，就是如果测试用例中如果存在 LONG_MIN ，那么我们无法写一个更小的值来实现上述逻辑。

于是有了下面优化版的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* pPre = nullptr;
    bool isValidBST(TreeNode* root) {
        //确定终止条件：空节点也是一种二叉搜索树
        if(!root) { return true; }

        //左孩子节点是二叉搜索树
        bool left = isValidBST(root->left);

        //左、中、右符合从小到大的顺序
        if(pPre != nullptr && pPre->val >= root->val) { return false; }
        pPre = root;

        //右孩子节点是二叉搜索树
        bool right = isValidBST(root->right);

        return left && right;
    }
};

这里的 pPre 的逻辑很绕很绕，要理解这个思路，我们应该采用理解上面的 maxVal 时的脑回路来理解这个解法，不要逐层递归往下无限代入去思考，我们只需要高屋建瓴地思考即可：

首先理解 pPre 的本质，就是用来表示 “上一个节点”，其在遍历完左子树后更新，更新后其指向【当前节点】然后再开始递归遍历右子树。所以在遍历右子树时，由于是中序遍历，先遍历左边节点，所以不会更新 pPre。即，当我们遍历右子树的左边时，pPre 仍然指向根节点。故可以避免 120 > 119 的情况。

# 21、530. 二叉搜索树的最小绝对差

  1. 思路 1：
    由于是二叉搜索树，所以自然而然想到其特性 —— 中序遍历的结果是有序的。
    所以我们的思路就是先对其中序遍历，然后对结果进行一次遍历求相邻元素的差值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
        int getMinimumDifference(TreeNode* root) {
            vector<int> result;
            stack<TreeNode*> st;
            TreeNode* node = root;

            while(node || !st.empty()) {
                if(node) {
                    st.push(node);
                    node = node->left;
                } else {
                    node = st.top(); st.pop();
                    result.push_back(node->val);
                    node = node->right;
                }
            }

            int ret = INT_MAX;
            for(int i = 1; i < result.size(); ++i) {
                int diff = result[i] - result[i-1];
                if(diff < ret) ret = diff;
            } return ret;
        }
    };

    中序遍历的迭代写法还是很不熟，可能是理解不到位，需要多写。

  2. 思路 2：
    同样的思路，但是用递归来写，就简单多了：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    private:
        void inorderTraversal(TreeNode* root, vector<int>& vec) {
            if(!root) return;
            if(root->left) {
                inorderTraversal(root->left, vec);
            }
            vec.push_back(root->val);
            if(root->right) {
                inorderTraversal(root->right, vec);
            }
        }
    public:
        int getMinimumDifference(TreeNode* root) {
            vector<int> result;
            inorderTraversal(root, result);
            int ret = INT_MAX;
            for(int i = 1; i < result.size(); ++i) {
                int diff = result[i] - result[i-1];
                if(diff < ret) ret = diff;
            } return ret;
        }
    };

# 22、501. 二叉搜索树中的众数

  1. 思路 1：
    由于题目进阶要求说不要使用额外空间，所以这里我只用了个 vector，没用其他诸如 set、map 之类的复杂结构。
    思路是，中序遍历，得到有序的数据，每次遍历时，计算当前数值出现的次数，次数大于最大记录，则更新最大记录，同时清空 vector，即更新，把当前数值作为可能的结果压入 vector。如果次数等于最大记录，由于可能存在多个众数，所以该值可能是可能的结果，故压入 vector，但不需要提前清空 vector，因为之前的数据也仍然有效。只有更新最大记录时需要更新清空 vector。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    public:
        vector<int> findMode(TreeNode* root) {
            int max_len = 0;
            int cur_mode = root->val;
            int cur_len = 0;

            vector<int> mode;
            stack<TreeNode*> st;
            TreeNode* node = root;
            while(node || !st.empty()) {
                if(node) {
                    st.push(node);
                    node = node->left;
                } else {
                    node = st.top(); st.pop();
                    if(node->val == cur_mode) {
                        ++cur_len;
                    } else {
                        cur_mode = node->val;
                        cur_len = 1;
                    }

                    if(cur_len > max_len) {
                        max_len = cur_len;
                        mode.clear();
                        mode.push_back(cur_mode);
                    } else if (cur_len == max_len) {
                        mode.push_back(cur_mode);
                    }
                    node = node->right;
                }
            } return mode;
        }
    };

这里有另一种写法，大差不差，维护一个 pre 指针，用于表示 “上一个节点”，然后在中序遍历过程中拿 pre 和 node 作比较即可，就不需要像上面那样维护 cur_mode 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        int max_len = 0;
        int cur_len = 0;

        vector<int> mode;
        stack<TreeNode*> st;
        TreeNode* node = root;
        TreeNode* pre = nullptr;

        while(node || !st.empty()) {
            if(node) {
                st.push(node);
                node = node->left;
            } else {
                node = st.top(); st.pop();
                if(!pre) {  // 第一个节点
                    cur_len = 1;
                } else if (pre->val == node->val) {
                    ++cur_len;
                } else {
                    cur_len = 1;
                }

                if (cur_len > max_len) {
                    max_len = cur_len;
                    mode.clear();
                    mode.push_back(node->val);
                } else if(cur_len == max_len) {
                    mode.push_back(node->val);
                }
 
                pre = node;
                node = node->right;
            }
        } return mode;
    }
};

但其实大同小异，思路都是相同的。

这里如果贪图方便的话，即不考虑进阶限制的内存要求，则可以用 set 之类的无脑进行统计，最后再处理分析即可。

  1. 思路 2：
    手贱点开官方题解看了一眼，发现有一个叫做 “Morris 中序遍历” 的高级东西。
    暂不展开 😃

# 23、236. 二叉树的最近公共祖先

  1. 思路 1：

没想出来...

思路是递归。
具体地，我们递归地向左右子树去遍历，如果找到 p、q 或遇到空指针则返回。
则有，当我们当前节点左右两个子树返回的结果都非空，则说明当前节点就是要找的目标节点。
如果其中一个节点为空，说明目标并不存在于该子树，则返回另一边的节点。
另外，注意，节点是逐层回溯向上传递上来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q || root == nullptr) { return root; }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left && right) { return root; }
        if(!left) { return right; }
        return left;
    }
};

  1. 思路 2：
    来自官方的题解。
    这个思路比较简单粗暴，我们维护一张哈希表，用于存储每个节点的父节点。先遍历一遍整棵二叉树，填哈希表。
    然后我们从 p 节点开始，沿着我们通过哈希表得到的 “血脉关系” 不断向上遍历父节点，把所有访问过的元素标记为已访问。
    （通过另一张哈希表实现标记）
    然后我们从 q 节点开始，同样沿着血脉向上遍历，同时判断当前节点是否曾经在遍历 p 时被标记过，是则找到目标。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        unordered_map<int, TreeNode*> parents;
        unordered_map<int, bool> seen;
        void dfs(TreeNode* root){
            if(root->left) {
                parents[root->left->val] = root;
                dfs(root->left);
            }
            if(root->right) {
                parents[root->right->val] = root;
                dfs(root->right);
            }
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            parents[root->val] = nullptr;
            dfs(root);
            while(p) {
                seen[p->val] = true;
                p = parents[p->val];
            }
            while(q) {
                if(seen[q->val]) return q;
                q = parents[q->val];
            } return nullptr;
        }
    };

# 24、235. 二叉搜索树的最近公共祖先

  1. 思路 1：
    这题抛开 “二叉搜索树” 的条件先不管，那么完全等同于上一题。所以上一题的两个思路都可以应用过来：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    private:
        TreeNode* findAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root == p || root == q || root == nullptr) return root;
            TreeNode* left = findAncestor(root->left, p, q);
            TreeNode* right = findAncestor(root->right, p, q);
            if(left && right) return root;
            if(left && !right) return left;
            return right;
        }


    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            return findAncestor(root, p, q);
        }
    };

    这里我是隔天做这道题，凭回忆把题解写出来了，一看就会，一写就对，不错不错～

  2. 思路 2：
    另一个思路同样地也是上一道题的题解，力扣官方题解之一：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
    private:
        void traversal(TreeNode* root, unordered_map<int, TreeNode*>& parents) {
            if(!root) return;
            if(root->left) parents[root->left->val] = root;
            if(root->right) parents[root->right->val] = root;
            traversal(root->left, parents);
            traversal(root->right, parents);
        }

    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            unordered_map<int, TreeNode*> parents;
            unordered_map<int, bool> seen;
            parents[root->val] = nullptr;
            traversal(root, parents);

            while(p) {
                seen[p->val] = true;
                p = parents[p->val];
            }

            while(q) {
                if(seen[q->val]) return q;
                q = parents[q->val];
            } return nullptr;
        }
    };

    我凭记忆把它写出来，一次就通过啦，真棒～

但是上面这两个题解都没用到 “二叉搜索树” 这个条件，是对条件的浪费。应该要有更优的解法才对。

  1. 思路 3：
    众所周知，二叉搜索树的特点就是有序。
    然后我们 “稍加思考”，就能发现，对于公共组先 x，满足 p->val < x->val < q->val ，且当该条件满足时，一定就是最近公共组先。于是我们可以利用这个特性，一次遍历就能找到目标（且并不需要遍历整棵树）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root->val > p->val && root->val > q->val) {
                return lowestCommonAncestor(root->left, p, q);
            } else if (root->val < p->val && root->val < q->val) {
                return lowestCommonAncestor(root->right, p, q);
            } else return root;
        }
    };

    这里用的是递归法，同样地，我们可以用递归法来写：

1
2
3
4
5
6
7
8
9
10
11
12
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 break;
        } return root;
    }
};

# 25、701. 二叉搜索树中的插入操作

  1. 思路 1：
    本来以为我的这个解法只能通过部分用例，没想到除了一个边界情况，其他全过了。
    思路就是，从根节点开始遍历二叉搜索树，判断当前节点的值与待插入的目标值 val 的关系，利用二叉搜索树的有序的特性，如果当前值偏大，则往左子树遍历，否则往右子树遍历。直到遍历的结果为空节点，则标明找到目标位置，在此插入节点即可。为了实现插入，实际上我们要从前一个节点开始判断下一个节点是否为空。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        TreeNode* insertIntoBST(TreeNode* root, int val) {
            if(!root) {
                root = new TreeNode(val);
                return root;
            }
            TreeNode* cur = root;
            while(cur) {
                if(cur->val > val) {
                    if(cur->left) {
                        cur = cur->left;
                    } else {
                        cur->left = new TreeNode(val);
                        break;
                    }
                } else {
                    if(cur->right) {
                        cur = cur->right;
                    } else {
                        cur->right = new TreeNode(val);
                        break;
                    }
                }
            } return root;
        }
    };

    （卧槽！写完去看题解，我居然写出了和官方题解几乎一模一样的写法。）

然后，上述代码可以通过递归的写法进行简化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) {
            return new TreeNode(val);
        }

        if(val < root->val) {
            root->left = insertIntoBST(root->left, val);
        } else {
            root->right = insertIntoBST(root->right, val);
        }

        return root;
    }
};

一下子简洁明了，这里， insertIntoBST 将返回值赋值给 left 或者 right，就相当于我们通过前节点来修改插入后节点。

另外，虽然这道题标的难度是中等，但感觉实际上是简单题。

# 26、450. 删除二叉搜索树中的节点

  1. 思路 1：

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回 nullptr 为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

这里第五种情况的处理方式我没想到，但是一旦知道了又很容易理解，实质上还是利用二叉搜索树的有序特性。

这里首先遍历查找 key 是否存在，大了往左，小了往右。
然后再根据情况进行节点替换，这里我们需要有一个变量 pre 记录先前节点，同时还要有一个 dir 记录方向，以方便改变先前节点的指向，用于重新指向新的值。

这里的边界条件，就是可能 root 就是我们要删除的对象，而 root 的 pre 为 nullptr，所以需要特殊处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    void repoint(TreeNode** root, TreeNode* pre, int dir, TreeNode* tobepoint) {
        if(!pre) {  // case we remove root
            *root = tobepoint;
        } else {
            if(dir) {
                pre->right = tobepoint;
            } else {
                pre->left = tobepoint;
            }
        }
    }

public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return root;
        // find node
        int dir = -1;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while(cur) {
            if(cur->val > key) {
                pre = cur;
                cur = cur->left;
                dir = 0;
            } else if (cur->val < key) {
                pre = cur;
                cur = cur->right;
                dir = 1;
            } else {
                break;
            }
        }

        // combine two tree
        if(!cur) return root;  // key doesn't exist
        if(cur->left && !cur->right) {
            repoint(&root, pre, dir, cur->left);
        }
        if(!cur->left && cur->right) {
            repoint(&root, pre, dir, cur->right);
        }
        if(!cur->left && !cur->right) {
            repoint(&root, pre, dir, nullptr);
        }
        if(cur->left && cur->right) {
            TreeNode* most_left = cur->right;
            repoint(&root, pre, dir, cur->right);
            while(most_left->left) {
                most_left = most_left->left;
            } most_left->left = cur->left;
        }
        delete cur;
        return root;
    }
};

当然，这里被我写复杂了。

  1. 思路 2：
    递归法，可以大大简化上面的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return root;
        if(root->val == key) {
            TreeNode* ret = nullptr;
            if(!root->left && !root->right) {
                //
            } else if(!root->left) {
                ret = root->right;
            } else if (!root->right) {
                ret = root->left;
            } else {
                TreeNode* most_left = root->right;
                while(most_left->left) {
                    most_left = most_left->left;
                } most_left->left = root->left;
                ret = root->right;
            }

            delete root;
            return ret;
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
        } else if (root->val < key) {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

这里，我们先看后半部分的代码，如果当前节点值偏大，我们知道要往左子树搜索，反之同理。这里我们用左右节点分别去接收递归函数的返回值，即，递归函数返回的内容就是我们要重新指向的位置。（这个回溯过程就大大简化了我们之前第一种写法中 pre、dir 的相关逻辑）。

当遍历到符合条件时，我们根据当前节点左右子树的关系，来决定返回什么内容。这里不再赘述。

# 27、669. 修剪二叉搜索树

两年前不会的题，如今还是不会。真不应该 😦

  1. 思路 1：

递归处理这个问题，这里我们还是围绕 “二叉搜索树有序” 的特点来处理。

对于当前节点，我们判断节点的值 val 与 low 和 high 的关系：
如果 val < low，说明当前节点 root 的左子树的数值就更是小于 low 了，属于要被裁剪的对象。
如果 val > high，说明当前节点 root 的右子树的数值就更是大于 low 了，也属于要被裁剪的对象。
那么这里的裁剪逻辑是怎么实现的呢？其实这里 “返回另一边子树” 就相当于 “裁掉了不符合要求的子树” 了
而至于挑选返回的这一边子树，是不是完全符合要求，未必，但我们交给下一轮递归来进行选择。
而如果，当前节点的值处于 (low, high) 范围内，当然也同样不等同于就结束了，我们还要递归地处理左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return nullptr;
        if(root->val < low) {
            return trimBST(root->right, low, high);
        } else if(root->val > high) {
            return trimBST(root->left, low, high);
        } else {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
        }
        return root;
    }
};

这个题解抄的力扣官方题解，官方好像也没对裁剪的节点进行 delete 释放内存，那就暂且不管了。

# 28、108. 将有序数组转换为二叉搜索树

这一题虽然到现在才遇到，但是在前面那些题的解题过程中，我一直想要实现这个功能，就能通过一次 “遍历原平衡二叉树” + 数据处理 + “重新生成平衡二叉树” 来解决一些问题了。

  1. 思路 1：
    这道题比较简单，这里我第一想到的方法就是递归，每一轮递归就找数组的中间位置的值作为新子树的根，然后该节点左右子节点就去接收递归调用的结果。

为了避免反复构造新的数组，所以这里我直接传递索引 start 和 end 来表示新数组的范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    TreeNode* traversal(vector<int>& nums, int start, int end) {
        if(start >= end) return nullptr;

        int mid = start + (end - start) / 2;
        TreeNode* cur = new TreeNode(nums[mid]);
        cur->left = traversal(nums, start, mid);
        cur->right = traversal(nums, mid+1, end);
        return cur;
    }


public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.empty()) return nullptr;
        return traversal(nums, 0, nums.size());
    }
};

这里我全程统一使用的是左闭右开区间。

# 29、538. 把二叉搜索树转换为累加树

  1. 思路 1：
    实际上这道题并不难。
    首先，二叉搜索树有序，左边的值小于中间的值，中间的值小于右边的值。
    根据题意，是从右向左累加，所以自然而然地，这道题要以 “右中左” 的顺序进行遍历，这一点大家都能想到。
    而累加，就是 “上一个值” + “当前值”，所以，我们只要通过一个 pre 变量记录 “上一个节点” 的值，然后每次遍历时加上该值即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    private:
        int pre = 0;
        void traversal(TreeNode* cur) {
            if(!cur) return;
            traversal(cur->right);
            cur->val += pre;
            pre = cur->val;
            traversal(cur->left);
        }
    public:
        TreeNode* convertBST(TreeNode* root) {
            pre = 0;
            traversal(root);
            return root;
        }
    };

    换成数组来思考更容易理解，二叉搜索树的中序遍历是一个递增数组，我们就是从数组尾端从头进行累加。
    那么换成二叉树也是一样的，只不过我们是在操作数，所以这个遍历比较抽象 —— 但我们已经知道是 “右中左” 的遍历顺序了。

在解这道题的时候，我犯了一个错误。 😦
我试图通过回溯的形式，从底往上进行累加。但这样不可行，虽然从右子树到中间节点的过程是自底向上的，但是从中间节点到左子树的过程又是自顶向下的。这样会遇到一个问题，就是左子树在递归时，从底往上累加回溯时返回的并非我们想要的结果，还需要带上根节点的值。

花了一两个小时写的下面的题解，但是连测试用例都过不了，主要是左子树在递归时，无法带上根节点的值进行累加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// class Solution {
// private:
//     int traversal(TreeNode* node) {
//         if(!node) return 0;
//         if(!node->left && !node->right) return node->val;
//         int right_tree_sum = traversal(node->right);
//         node->val += right_tree_sum;
//         if(node->left) {
//             node->left->val += node->val;
//         }
//         int left_tree_sum = traversal(node->left);
//         if(node->left) {
//             return node->left->val;
//         } else {
//             return node->val;
//         }
//     }

// public:
//     TreeNode* convertBST(TreeNode* root) {
//         if(!root) return nullptr;
//         traversal(root);
//         return root;
//     }
// };

至此，二叉树的基本练习就告一段落。基本上，对于二叉树的题目，如果一上来没什么思路，就可以想尝试着用递归去拆分问题，或许就能够直接解决。递归相较于迭代，在处理一些问题时，不但更容易理解，而且可以通过递归的返回值来实现 “改变前一个节点的指向” 的问题。另外，我们也可以用一个 pre 变量来标示 “上一个” 状态，对此我们也做了几道相关的题，需要熟悉，不然的话用迭代法会很麻烦。

关于二叉搜索树的题，基本上都是利用了其有序的特点，一定要善用这个条件，题目不会无缘无故强调二叉搜索树。

二叉树的基础，即几种遍历方式，需要熟悉。无论是层序遍历，还是递归、迭代法的各种顺序的遍历。在中等难度的题目中，遍历顺序都已经变成一个微不足道的小细节，隐藏在题解中。有时候顺序对于解题很重要，有时候却又不重要。

另外，递归就意味着会有回溯，虽然我们在这一系列的题目里严格意义上来说只遇到过两次，但要了解。

更新于

请我喝杯咖啡吧~

Rick 微信支付

微信支付

Rick 支付宝

支付宝