110. Balanced Binary Tree
程序员文章站
2022-05-18 19:53:04
...
problems:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
tips:
判断二叉树是否为高度平衡二叉树,即它的两个子树每个节点的深度之差都不大于1.
solutions:
1.超时,但是逻辑清晰简单,便于理解下一个方法。
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
if(!isBalanced(root->left)) return false;
if(!isBalanced(root->right)) return false;
int left = depth(root->left);
int right = depth(root->right);
if(abs(left-right)>1)
return false;
return true;
}
int depth(TreeNode* root)
{
if(!root) return 0;
return max(depth(root->left),depth(root->right))+1;
}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
return depth(root)!=-1;
}
int depth(TreeNode* root)
{
if(!root) return 0;
int left = depth(root->left);
int right = depth(root->right);
if(left == -1 || right == -1 || abs(left-right)>1)//不平衡时为-1
return -1;
return max(left,right)+1;
}
};
推荐阅读
-
LC 297 Serialize and Deserialize Binary Tree
-
leetcode笔记:Invert Binary Tree
-
Convert Sorted Array to Binary Search Tree
-
minimum-depth-of-binary-tree
-
cf438E. The Child and Binary Tree(生成函数 多项式开根 多项式求逆)
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
Leetcode——108. Convert Sorted Array to Binary Search Tree
-
Leetcode 108. Convert Sorted Array to Binary Search Tree
-
21天刷题计划之17.1—maximum-depth-of-binary-tree(二叉树的最大深度)(Java语言描述)
-
21天刷题计划之18.1—balanced-binary-tree(平衡二叉树)(Java语言描述)