leetcode_day17
本文最后更新于 2024年6月7日 下午
今日内容:
● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
平衡二叉树
只是判断平衡二叉树,比较简单,按规范化思路来吧,避免一会有感觉秒了,一会没感觉卡了
递归结束条件:如果左子树不是平衡二叉树 或者 右子树不是平衡二叉树 或者 左右子树深度差距大于1
递归操作:判断左子树是不是平衡二叉树,判断右子树是不是平衡二叉树,获取左右子树深度
参数及返回值:根节点 + 是否合法的bool值
原创AC代码: 1
2
3
4
5
6
7
8
9
10
11
12bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;//空视作平衡
if(isBalanced(root->left) && isBalanced(root->right)) {//左右都是
return abs(getDepth(root->left) - getDepth(root->right)) <= 1;//左右深度是否匹配
}
else return false;
}
int getDepth(TreeNode * root) {
if(root == nullptr) return 0;//空树深度0
int ans = 1;
return max(getDepth(root->left), getDepth(root->right)) + 1;//左右子树最大深度加自己
}
自底向上做法: 1
2
3
4
5
6
7
8
9
10
11
12bool isBalanced(TreeNode* root) {
if(root == nullptr) return true;
return getDepth(root) != -1;
}
int getDepth(TreeNode * root) {
if(root == nullptr) return 0;
int left = getDepth(root->left);
if(left == -1) return -1;//只要一个子树不平衡,整个树就不平衡
int right = getDepth(root->right);
if(right == -1) return -1;
return abs(left - right) <= 1 ? max(left, right) + 1 : -1;
}
二叉树的所有路径
递归三步:
- 参数&返回值
无需返回值,参数有根节点和存路径和答案的数组
- 递归终止条件
遇到叶节点
- 递归逻辑
没遇到就接着往里插
比较简单,贴代码: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
vector<string> ans;
vector<string> binaryTreePaths(TreeNode* root) {
if(!root) return {};
string line;
traversal(root, line);
return ans;
}
void traversal(TreeNode * root, string s) {
s += to_string(root->val);
if(!root->left && !root->right) ans.push_back(s);
else {
s += "->";
if(root->left) traversal(root->left, s);
if(root->right) traversal(root->right, s);
}
}
};
迭代写法
用一个栈存节点,一个栈存目前已经走过的路径 注意push根节点和其他节点的差异
1 |
|
左叶子之和
需要注意,单独一个根节点不能称作左叶子,只是叶子,但不左
1 |
|
这个递归看得有点懵,后面再来仔细理解一下吧