题目描述
输入一棵二叉树的根结点,判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。
注意:
规定空树也是一棵平衡二叉树。
样例
输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,
5
/ \
7 11
/ \
12 9
输出:true
算法1
(递归) $O(logn)$
平衡二叉树是一种递归定义。可沿用上一题求二叉树深度递归方法,
在每一层递归时候判断下 左右子树高度差是否>1
C++ 代码
class Solution {
public:
int ans = true;
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root){
if(!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
if(abs(left - right) > 1) ans = false;
return max(left, right) + 1;
}
};