leetCode ✏Leetcode基础刷题之(110. Balanced Binary Tree)
✏描述
给定一个二叉树，判断它是否是一棵平衡二叉树。平衡二叉树的定义是：每一节点的两个子树的高度相差不能超过1。
✏题目实例
3
/ \
9 20
/ \
15 7
上图中符合高度差不大于1的要求。
1
/ \
2 2
/ \
3 3
/ \
4 4
上图中根节点1的左右子树的高度差已然超过1，所以它不是平衡二叉树。
✏题目分析
如果是空树的话，那么是正确的，否则递归他的左右子树进行比较，最后用return -1来表示不平衡，下面是具体php实现代码。
/**
* @param TreeNode $root
* @return Boolean
*/
function isBalanced($root) {
return $this->high($root) !==-1;
}
function high($root){
if(!$root){
return 0;
}
$left=$this->high($root->left);
$right=$this->high($root->right);
if($left==-1 ||$right==-1 || abs($left-$right)>1){
return -1;
}
return max($left,$right)+1;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)