OJ刷题总结5——二叉树递归
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
两颗树相同，意味着当前的两个节点相同，并且当前两个的左右子树相同。
那么结束条件呢？当递归到空节点时，判断两者是否相同即可。
1
2
3
4
5
6
7
| class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!q || !p) return p == q;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
|
给你一个二叉树的根节点 root ， 检查它是否轴对称。
就是检查当前根节点的左右两颗子树，是否对称。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool isSame(TreeNode* left, TreeNode* right) {
if (!left || !right) {
return left == right;
}
return left->val == right->val && isSame(left->right, right->left) && isSame(left->left, right->right);
}
bool isSymmetric(TreeNode* root) {
return isSame(root->left, root->right);
}
};
|
给定一个二叉树，判断它是否是平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int getHeight(TreeNode* root) {
if (!root) return 0;
int left_height = getHeight(root->left);
if (left_height == -1) return -1;
int right_height = getHeight(root->right);
if (right_height == -1 || abs(left_height - right_height) > 1) return -1;
else return max(left_height, right_height) + 1;
}
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(root, depth):
if (root is None):
return
if (depth == len(ans)):
ans.append(root.val)
dfs(root.right, depth + 1)
dfs(root.left, depth + 1)
dfs(root, 0)
return ans
|
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
需要注意的是，不能直接
1
2
| root->left = invertTree(root->right);
root->right = invertTree(root->left);
|
否则这样就是，右边翻转，赋给左子树；左子树再翻转，赋给右子树，但是这里的左子树已经被翻转了。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return NULL;
auto inv_right = invertTree(root->right);
auto inv_left = invertTree(root->left);
root->left = inv_right;
root->right = inv_left;
return root;
}
};
|
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
我们可以在递归时，维护两个变量，分别为mx，mn；其含义是祖先节点到当前节点的最大/最小的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int ans = 0;
void dfs(TreeNode* root, int mx, int mn) {
if(!root) return;
mx = max(mx, root->val);
mn = min(mn, root->val);
ans = max(ans, root->val - mn);
ans = max(ans, mx - root->val);
dfs(root->left, mx, mn);
dfs(root->right, mx, mn);
}
int maxAncestorDiff(TreeNode* root) {
dfs(root, root->val, root->val);
return ans;
}
};
|
给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。
假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。
叶子节点，就是没有子节点的节点。
有几个点可以简单理解一下：
- “不足节点”，需要被删除，那么怎么个删除法呢？我的想法是在递归时，返回NULL
- 叶子节点，等价于其
left == NULL && right == NULL
- 由于是二叉树，如果一个内部节点的左孩子和有孩子都返回NULL，那么这个节点也是不足节点。返回NULL，有2层含义，一是这个内部节点仅有1个孩子，那么它肯定会收到一个NULL，剩下的那个NULL则是因为它是不足节点；二是，他有两个孩子，两个孩子都返回了NULL，两个都是不足节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
TreeNode* dfs(TreeNode* root, int sum, const int limit) {
if (!root) return NULL;
sum += root->val;
if(!root->right && !root->left) {
if(sum >= limit) return root;
else return NULL;
}
root->left = dfs(root->left, sum, limit);
root->right = dfs(root->right, sum, limit);
if (root->left == NULL && root->right == NULL) return NULL;
else return root;
}
TreeNode* sufficientSubset(TreeNode* root, int limit) {
return dfs(root, 0, limit);
}
};
|
