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); } };
|