LeetCode 110. Balanced Binary Tree
程序员文章站
2024-03-19 19:13:50
...
题目描述
知识点
二叉树递归自底向上 + 提前隔断
结果
这个程度的时空复杂度可以啦
实现
码前思考
- 由于涉及到了高度,所以一定要有高度这个变量,由于
TreeNode
结构体定死了,所以我们采用局部变量来存储左右子树的高度,然后就是简单的判断即可。
代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//递归判断当前的树是否是否是平衡二叉树
//对于这种true or false的题目,常见的递归式就是左右子树的&&运算
//需要记录子树的高度
class Solution {
private:
bool flag;
public:
bool isBalanced(TreeNode* root) {
//注意空树是否需要判断
flag = true; //初始化为true
//记录左子树和右子树的高度
int height;
judge(root,height);
return flag;
}
//判断当前以root为根的树是否是平衡二叉树,height表示当前子树的高度
int judge(TreeNode* root,int& height){
if(root == NULL){
height = 0;
}else if(flag == true){ //设置一个true判断,一定程度上减少不必要的递归
//记录左子树和右子树的高度
int lHeight;
int rHeight;
judge(root->left,lHeight);
judge(root->right,rHeight);
height = max(lHeight,rHeight) + 1;
if(abs(lHeight - rHeight) > 1){
flag = false;
}
}
return height;
}
};
码后反思
- 看了题解,发现自己使用的是自底向上的方法来判断,而且还是使用了一个
bool
变量flag
来进行提前的隔断。
推荐阅读
-
LeetCode 110. Balanced Binary Tree
-
【LeetCode】Balanced Binary Tree(平衡二叉树)
-
leetcode--minimum-depth-of-binary-tree
-
[Leetcode][python]Minimum Depth of Binary Tree
-
LeetCode:102.Binary Tree Level Order Traversal
-
LeetCode 662 Maximum Width of Binary Tree 二叉树的最大宽度
-
[leetcode]662. Maximum Width of Binary Tree(Python)
-
Leetcode Maximum Depth of Binary Tree
-
leetcode【104】Maximum Depth of Binary Tree
-
LeetCode------Maximum Depth of Binary Tree