Balanced Binary Tree
Question
- leetcode: Balanced Binary Tree | LeetCode OJ
- lintcode: (93) Balanced Binary Tree
Problem Statement
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
Given binary tree A={3,9,20,#,#,15,7}
, B={3,#,20,15,7}
1 | A) 3 B) 3 |
The binary tree A is a height-balanced binary tree, but B is not.
题解1 - 递归
根据题意,平衡树的定义是两子树的深度差最大不超过1,显然使用递归进行分析较为方便。既然使用递归,那么接下来就需要分析递归调用的终止条件。和之前的 Maximum Depth of Binary Tree | Algorithm 类似,NULL == root
必然是其中一个终止条件,返回0
;根据题意还需的另一终止条件应为「左右子树高度差大于1」,但对应此终止条件的返回值是多少?——INT_MAX
or INT_MIN
?想想都不合适,为何不在传入参数中传入bool
指针或者bool
引用咧?并以此变量作为最终返回值,此法看似可行,先来看看鄙人最开始想到的这种方法。
C++ Recursion with extra bool variable
1 | /** |
源码解析
如果在某一次子树高度差大于1时,返回INT_MAX
以减少不必要的计算过程,加速整个递归调用的过程。
初看起来上述代码好像还不错的样子,但是在看了九章的实现后,瞬间觉得自己弱爆了... 首先可以确定abs(leftDepth - rightDepth) > 1
肯定是需要特殊处理的,如果返回-1
呢?咋一看似乎在下一步返回max(leftDepth, rightDepth) + 1
时会出错,再进一步想想,我们能否不让max...
这一句执行呢?如果返回了-1
,其接盘侠必然是leftDepth
或者rightDepth
中的一个,因此我们只需要在判断子树高度差大于1的同时也判断下左右子树深度是否为-1
即可都返回-1
,不得不说这种处理方法要精妙的多,赞!
C++
1 | /** |
Java
1 | /** |
源码分析
抓住两个核心:子树的高度以及高度之差,返回值应该包含这两种信息。
复杂度分析
遍历所有节点各一次,时间复杂度为 \[O(n)\], 使用了部分辅助变量,空间复杂度 \[O(1)\].
Balanced Binary Tree