思想
二叉树，和前面讲的回溯法或者二分查找相比，不可同日而语。二叉树不是一个方法，而是一个场景，回溯法和二分查找都是方法，因此有一套模板，而关于二叉树，或许只能概括在这个舞台上，有哪些好戏会上演，难以找到一个 silver bullet。
题目
94. Binary Tree Inorder Traversal
这道题是基础的二叉树中序遍历题目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
private:
vector<int> result;
public:
vector<int> inorderTraversal(TreeNode* root) {
if (!root) return {};
inorderTraversal(root->left);
result.push_back(root->val);
inorderTraversal(root->right);
return result;
}
};
|
递归的解法是平凡的，没什么好说的。记住中序遍历是左-中-右（即根结点在中间）就好。题目要求我们用循环的方式来解决，那需要模拟递归。
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:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top(); st.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}
};
|
思路是这样的：在进行中序遍历的时候，我们一开始会贪心地遍历到整棵树的最左侧，直到撞上南墙。这时候 curr 是 nullptr。随后，从栈中取出栈顶，这就是当前该访问的结点，记录它，并设置下一步访问它的右孩子。
何时循环终止？curr 是空，且整个栈也空了，那就说明遍历完毕整棵树。
98. Validate Binary Search Tree
这道题让我们验证一棵树是不是二叉搜索树。一棵合法的二叉搜索树，左子树的所有结点值严格小于根的，且右子树的所有值严格大于根的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
private:
long long prev = LLONG_MIN;
public:
bool isValidBST(TreeNode* root) {
if(!root) return true;
if (!isValidBST(root->left)) return false;
if (root->val <= prev) return false;
prev = root->val;
return isValidBST(root->right);
}
};
|
和 BST 相关的一个好用的结论是：如果中序遍历一棵合法的二叉搜索树，得到的是严格递增的数列。上面的解法就是在使用这个性质，先处理左孩子，再处理根，最后处理右孩子。
需要注意的有两点：
- 需要判断根是否为空，否则访问左右孩子没有意义；
prev 的初值需要开 long long，否则用例会过不去。
而另一种解法则比较直观：既然是二叉搜索树，根据定义，我应该检查是不是这棵树的左子树和右子树都满足上下界：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
private:
bool validRange(TreeNode* root, long long left, long long right) {
if (!root) return true;
if (!(left < root->val && root->val < right)) return false;
return validRange(root->left, left, root->val) && validRange(root->right, root->val, right);
}
public:
bool isValidBST(TreeNode* root) {
return validRange(root, LLONG_MIN, LLONG_MAX);
}
};
|
或许这题给我们的启示是：记得开 long long。
101. Symmetric Tree
这棵树要求我们判断一棵树是不是对称的。
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) return true;
queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);
while (!q.empty()) {
TreeNode* l = q.front(); q.pop();
TreeNode* r = q.front(); q.pop();
if (!l && !r) continue;
if (!l || !r) return false;
if (l->val != r->val) return false;
q.push(l->left);
q.push(r->right);
q.push(l->right);
q.push(r->left);
}
return true;
}
};
|
核心思想是需要设置两个指针，分别指向树的两侧需要检查的位置。这两个指针可能有几种情形：
- 全为空 -> 考虑下一对；
- 有一个为空 -> 不对称；
- 全不为空但值不同 -> 不对称；
- 值相同 -> 考虑孩子。
加入孩子进入队列时，也需要按照镜面的方式来考虑。左侧指针的左孩子要和右侧指针的右孩子进行比较；另一种情况同理。这样才符合镜面的定义。
这道题是个 Easy，但我认为如果之前没有见过，想不到双指针的情形，或者不知道该如何处理对称，其实没那么容易。
102. Binary Tree Level Order Traversal
这道题要求我们进行二叉树的层次遍历。
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
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> result;
if (!root) return {};
q.push(root);
while (!q.empty()) {
int sz = q.size();
vector<int> line;
for (int i = 0; i < sz; i++) {
TreeNode* curr = q.front(); q.pop();
line.push_back(curr->val);
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
result.push_back(line);
}
return result;
}
};
|
如果说中序遍历用栈模拟，那层次遍历就用队列来模拟。我们需要记录队列，以及这一层的结点数量。这样，随着遍历的进行，队列中的结点增增减减，但我们始终不忘初心，记得队列在这层遍历开始前结点的数量。
当然老样子，也是记得判断 root 不是 nullptr。
104. Maximum Depth of Binary Tree
这道题要求我们求出二叉树的最大深度。
1
2
3
4
5
6
7
8
| class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
|
这题更是可以一发入魂。到底二叉树的树深定义是什么？对于这个结点来说，应该是左子树的深度与右子树深度的最大值，再加一。如果当前结点为空，则树深为 0。递归代码忠实地反映了上述定义。
105. Construct Binary Tree from Preorder and Inorder Traversal
这道题给了我们二叉树的先序遍历和中序遍历，要求我们重新构建出这棵树。
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 {
private:
unordered_map<int, int> index;
TreeNode* build(vector<int>& preorder, int preL, int preR, vector<int>& inorder, int inL, int inR) {
if (preL > preR) return nullptr;
int curVal = preorder[preL];
TreeNode* curr = new TreeNode(curVal);
int k = index[curVal];
int leftSize = k - inL;
curr->left = build(preorder, preL + 1, preL + leftSize, inorder, inL, k - 1);
curr->right = build(preorder, preL + leftSize + 1, preR, inorder, k + 1, inR);
return curr;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); i++) {
index[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
};
|
如果是数据结构与算法的期末考试题，让我手写出来，是非常简单的，然而如果让我用算法来准确表述，说句实话，有些困难。这两者之间的 gap 表明对于树的构造算法并没有很熟悉。
树的构造是个递归的过程，对于每个结点，需要考虑如下几件事情：
- 它的值是什么；
- 它的左子树、右子树范围是什么；
- 对应的子树范围如何反映到
pre/inorder 向量的下标范围中，从而完成孩子的递归构造。
我们就分析上面代码的 build 递归的部分。什么时候构造结束呢？左侧边界比右侧大，表示结束。有人说，一定要 preL > preR 吗？其实不然，inL > inR 也是可以的。
那么，对于当前这个结点以及输入的向量和范围，哪个值是当前结点的值？
对于这个问题，我觉得首先要做一个思维上的转变，不要认为输入是向量 + 左右边界，而就是一个向量。这个向量是 原始向量[left, right] 闭区间取得的。这样的话，对于边界的含义也更加清晰，更符合递归的思路。
好，那么现在我有一个结点，以及对应的 preorder 和 inorder，它的值是什么？显然——是 preorder 的第一个元素！好，问题 1 解决了。
下面要确定左右子树的划分了，这一步，需要 inorder 向量发挥作用。定位到当前元素在 inorder 向量的位置，其左侧是左子树，右侧是右子树（不含当前结点）。这就是为什么我们需要初始化一个 index，也是这种子树构造必须提供中序遍历的原因。
这样，中序遍历的子树范围是最好确定的，那，先序的怎么办呢？很好理解，先序遍历是什么顺序来着？中-左-右！那，可以理解为，先遍历根结点，再遍历整个左子树（不管内部顺序）这堆结点，再遍历右子树这堆。
大功告成！先序遍历中，左子树的范围应该是从当前结点开始，到 leftSize 偏移量；右子树的范围则是左子树的右边界 + 1，到当前边界的末尾。
Follow up：如果提供给你后序遍历和中序遍历的向量，你能还原一棵树吗？
这个后续问题和本题的区别是，后序遍历是左-右-中的顺序。那么还是刚刚的三个问题。
给了两个向量，当前值是什么？得从后序遍历入手了，当前值应该是后续向量的最后一个。那，左右子树的范围呢？中序还是老样子没变化，而后序遍历中，左子树的范围是 [postL, postL + leftSize - 1]；右子树是左子树的右边界 + 1 到 postR - 1。
108. Convert Sorted Array to Binary Search Tree
这题给了我们一个有序数组，让我们转化为平衡的二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private:
TreeNode* build(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = build(nums, left, mid - 1);
node->right = build(nums, mid + 1, right);
return node;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
};
|
有序数组和二叉搜索树有什么关系？是树被压平了的体现。这样的话，在构建树的时候，取中点作为根，随后递归构造左子树和右子树，看上去就没问题了。
114. Flatten Binary Tree to Linked List
这题要求我们，把一棵二叉树展平为一个链表，或者说右深树。要求这颗右深树相当于先序遍历这棵树的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private:
TreeNode* prev = nullptr;
public:
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
flatten(root->left);
root->left = nullptr;
root->right = prev;
prev = root;
}
};
|
这题算是个找规律的题目。现在它希望我展平原来的数组，使得顺序和先序（中左右）一样。方式是按照右左中的顺序来遍历并修改指针。
而如果想让顺序和中序（左中右）一样，则按照右中左的顺序来遍历；后序则是中右左。后两种情况，就需要注意保存中的孩子，否则修改指针后就丢掉了。
算是玩弄二叉树规律的题目。
124. Binary Tree Maximum Path Sum
这道题要求我们求出二叉树中最大的路径和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
private:
int ans = INT_MIN;
int dfs(TreeNode* node) {
if (!node) return 0;
int left = max(0, dfs(node->left));
int right = max(0, dfs(node->right));
ans = max(ans, left + right + node->val);
return max(left, right) + node->val;
}
public:
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};
|
这题是二分搜索里被错误分类的那一道，一个 Hard，放到这里来。这道题，我觉得有几个地方可以总结：
- 路径和 437 中的不一样，后者是前缀和的思想，这里是递归，需要品一品；
- 思想和 543 类似，都是在递归的过程中维护一个全局
ans 最后返回；
- 计算路径和，考虑左边值和右边值，必须加上当前结点值，这样才能连通起来；在返回值的时候，只能选择左右较大的一边加上该结点的值来返回，因为路径不能分叉。
199. Binary Tree Right Side View
这题要求我们自上而下地返回一棵二叉树从右侧观看时，能看到的结点。
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:
vector<int> rightSideView(TreeNode* root) {
if (!root) return {};
vector<int> result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* now = q.front(); q.pop();
if (now->left) q.push(now->left);
if (now->right) q.push(now->right);
if (i == sz - 1) result.push_back(now->val);
}
}
return result;
}
};
|
本质上是层次遍历，只不过保留层次遍历每层的最后一个元素。稍微改一改，还可以返回左侧视角。
226. Invert Binary Tree
这题要求我们翻转二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
invertTree(root->left);
invertTree(root->right);
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
return root;
}
};
|
简单的递归，没什么好说的。
230. Kth Smallest Element in a BST
要求我们找出一棵二叉搜索树中第 k 个最小的元素。
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
| class Solution {
private:
int num;
int _k;
int inorder(TreeNode* node) {
if (!node) return -1;
int res = inorder(node->left);
if (res >= 0) return res;
num++;
if (num == _k) {
return node->val;
}
res = inorder(node->right);
if (res >= 0) return res;
return -1;
}
public:
int kthSmallest(TreeNode* root, int k) {
num = 0;
_k = k;
return inorder(root);
}
};
|
方法是利用 BST 的性质：中序遍历得到递增序列。至于说怎么中序遍历，可以用递归的方法，也可以用循环来控制。看喜欢哪种方式了。这样来看，循环中序遍历确实是基础中的基础。
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 kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> st;
TreeNode* curr = root;
int num = 0;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top(); st.pop();
num++;
if (num == k) return curr->val;
curr = curr->right;
}
return -1;
}
};
|
236. Lowest Common Ancestor of a Binary Tree
这题让我们找出树中的两个结点的最低共同祖先。
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 || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
};
|
说起来这道题，我记得学算法的时候，学校的 OJ 也有这道题，我当时完全是暴力的做法，好像花了一个上午才完成一道题目，给我累的不行。
其实这道题的解法很巧妙：对于一个结点，分别在它的左右子树试图寻找目标，如果在两边都找到了，那它就是最小祖先；如果只在一边找到了，那这一边就是最小的共同祖先。
一个自然的疑问是，这个递归是怎样跨越层次来找到祖先的？
如果在两侧都能找到，毫无疑问，它肯定是我们要找的这个祖先了，但关键是，怎么把这个信息层层上报？
这个递归函数的返回值的语义是：距离两个目标最近的祖先。这样就清楚了。从根开始，问问左结点，问问右结点。左结点如果找到，会返回其中一个目标的最小祖先；右结点同理，可能会返回另一个目标的最小祖先。
如果这两个祖先都找到了，那说明，当前结点是分叉点，是共同的最小祖先。如果只在一侧找到，说明那一侧返回的最小祖先是共同最小祖先。层层递归，信息就上去了。
还是要再悟。
我想起来，当时之所以 OJ 写这么久，可能因为要手动处理输入输出，诶，麻烦死。
437. Path Sum III
这题要求我们找出等于目标的树上路径。路径必须从上到下走。
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:
unordered_map<long long, int> cnt;
int ans;
int target;
void dfs(TreeNode* node, long long currSum) {
if (!node) return;
currSum += node->val;
if (cnt.count(currSum - target)) {
ans += cnt[currSum - target];
}
cnt[currSum]++;
dfs(node->left, currSum);
dfs(node->right, currSum);
cnt[currSum]--;
}
public:
int pathSum(TreeNode* root, int targetSum) {
ans = 0;
cnt[0] = 1;
target = targetSum;
dfs(root, 0);
return ans;
}
};
|
这题是个前缀和的题目，有些难度在的。关键的思想是，所谓的每一条路径，实际上是两条前缀和路径的差值。
因此，我们要维护一个字典，记录每个前缀和出现的次数。同时，在进行 dfs 时，需要记录当前前缀和的值是多少。这样，有了当前信息和历史信息，就能得出满足目标值的路径个数。
当然，和回溯法的思想类似，在递归前，修改状态，递归后要还原状态。以及，前缀和为 0 的路径初始化有 1 条，即空路径。最后，记得开 long long。
543. Diameter of Binary Tree
这题要求我们找到一棵二叉树的直径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private:
int ans;
int depth(TreeNode* root) {
if (!root) return 0;
int left = depth(root->left);
int right = depth(root->right);
ans = max(ans, left + right);
return max(left, right) + 1;
}
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 0;
depth(root);
return ans;
}
};
|
是个简单的递归，但是具体的写法怎样才好看，还是要琢磨一下。边统计深度，边计算答案，还不错。那，可以认为是树深那道题的变体了。
