关于检查Binary tree是否balanced - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于检查Binary tree是否balanced

关于检查Binary tree是否balanced# JobHunting - 待字闺中

I*y2014-11-23 08:11

1 楼

书上说的recursive方法是每一步判定
1）左边subtree是否balanced
2）右边subtree是否balanced
3）左边的subtree height与右边subtree height是否最多相差1
我想问一下如果这样做有什么问题：
1）recursively求出整个tree的maximum height O(n)
2) recursively求出整个tree的minimum height O(n)
3) 检查两个高度是否最多差1
我是算法弱人，求大牛指点。

h*k2014-11-23 08:11

2 楼

1）recursively求出整个tree的maximum height O(n)
可以实现
2) recursively求出整个tree的minimum height O(n)
min只能用bfs求出吧，你如何用recursion求出

s*i2014-11-23 08:11

3 楼

主要是很多情况不需要计算出整个tree的高度的时候，已经知道它不是balanced 的了
（fail fast)。而你的这个算法会浪费时间还在计算。

【在 I*********y 的大作中提到】

: 书上说的recursive方法是每一步判定
: 1）左边subtree是否balanced
: 2）右边subtree是否balanced
: 3）左边的subtree height与右边subtree height是否最多相差1
: 我想问一下如果这样做有什么问题：
: 1）recursively求出整个tree的maximum height O(n)
: 2) recursively求出整个tree的minimum height O(n)
: 3) 检查两个高度是否最多差1
: 我是算法弱人，求大牛指点。

I*y2014-11-23 08:11

4 楼

min 也可以recursive地求出，跟求max接近.
public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null) return minDepth(root.right) + 1;
if (root.right == null) return minDepth(root.left) + 1;
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

【在 h***k 的大作中提到】

: 1）recursively求出整个tree的maximum height O(n)
: 可以实现
: 2) recursively求出整个tree的minimum height O(n)
: min只能用bfs求出吧，你如何用recursion求出

I*y2014-11-23 08:11

5 楼

我明白，你是说用BFS找第一个leaf node，找到就停，这个对于unbalanced tree比较
快。
我就是想知道用min 和 max这种方法是不是有可能不正确。如果正确的话，也算是一个
O(N)的候选方法，虽然对于unbalanced tree可能慢些。

了

【在 s*i 的大作中提到】

: 主要是很多情况不需要计算出整个tree的高度的时候，已经知道它不是balanced 的了
: （fail fast)。而你的这个算法会浪费时间还在计算。

b*g2014-11-23 08:11

6 楼

1
/ \
2 3
/ \ / \
4 5 6 7
/ / \ / \
8 9 10 11 12
/
13
这树算不算平衡？
写字板打树好累-_-!

I*y2014-11-23 08:11

7 楼

哇，太感谢了！这树应该是平衡的。但是min和max差2，真的是个反例，看来我的方法
错了，还是老老实实地按照定义做，不能投机取巧。

【在 b******g 的大作中提到】

: 1
: / \
: 2 3
: / \ / \
: 4 5 6 7
: / / \ / \
: 8 9 10 11 12
: /
: 13
: 这树算不算平衡？

b*g2014-11-23 08:11

8 楼

是的。同是算法弱人，我觉得在理解这种本身是递归性的定义时要特别当心。因为递归
性的定义本身理
解比较困难，如果真的有更简单明了的定义，那恐怕教科书上就不这么定义了。构造这
个反例的思路是：
平衡时left subtree L和right subtree R最大高度最多差1，假设分别为n和n+1
而对于L本身来说，要它平衡，L to leave的高度却可以是n或n-1。造成这个现象的原
因其实就在于平衡定义中这个“最大高度”上。

【在 I*********y 的大作中提到】

: 哇，太感谢了！这树应该是平衡的。但是min和max差2，真的是个反例，看来我的方法
: 错了，还是老老实实地按照定义做，不能投机取巧。

F*o2014-11-23 08:11

9 楼

I do not think this is a balanced BT. see definition:
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.
It is"two subtrees", not "left subtree and right subtree".
You can use min and max method

【在 I*********y 的大作中提到】

: 哇，太感谢了！这树应该是平衡的。但是min和max差2，真的是个反例，看来我的方法
: 错了，还是老老实实地按照定义做，不能投机取巧。

b*02014-11-23 08:11

10 楼

明显你自己理解错了...

depth

【在 F*****o 的大作中提到】

: I do not think this is a balanced BT. see definition:
: 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.
: It is"two subtrees", not "left subtree and right subtree".
: You can use min and max method

b*g2014-11-23 08:11

11 楼

定义是对的。但是left/right subtree和每个node的two subtree是一回事。left/
right subtree并不特指是root的。而定义中的two subtree也必须属于同一个node下。
我举的那个反例里你能找出哪个node下的two subtree高度差1以上吗？

depth

【在 F*****o 的大作中提到】