如何确定二叉树是否平衡?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (19)

我在想这件事情:

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

这是一个很好的实现吗?或者我错过了什么?

提问于
用户回答回答于

平衡是一个真正微妙的属性; 你以为你知道它是什么,但很容易出错。特别是,即使Eric Lippert的(好)答案也没有。那是因为身高的概念还不够。你需要树的最小和最大高度的概念(其中最小高度是从根到树叶的最少步数,最大值是...呃,你得到的图片)。鉴于此,我们可以将平衡定义为:

一棵树在那里的任何分支的最大高度不超过一个比任何分支的最小高度以上。

(这实际上意味着分支本身是平衡的;您可以选择最大和最小分支。)

所有你需要做的事情来验证这个属性是一个简单的树遍历,跟踪当前的深度。第一次回溯时,这会给你一个基线深度。每次在您回溯之后,您都会将新的深度与基线进行比较

  • 如果它等于基线,那么你就继续
  • 如果它不止一个,树就不平衡
  • 如果它是一次性的,那么你现在知道平衡的范围,并且所有随后的深度(当你要返回时)必须是第一或第二个值。

在代码中:

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    }
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            o.before();
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
                o.after();
            }
        }
    }
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                    }
                }
                return true;
            }
        });
    }
}

我想你可以在不使用观察者模式的情况下做到这一点,但我发现这样更容易推理。

用户回答回答于

解决这个问题的方法是首先为你正在编写的函数编写一个规范。

规范:一个格式良好的二叉树被称为“高度平衡”,如果(1)它是空的,或(2)它的左右儿童是高度平衡的,并且左边树的高度在正确的树的高度。

现在你已经具备了这个规范,代码很容易编写。只需遵循规范:

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

扫码关注云+社区