0

检查二叉树是否平衡。

CTCI 5th上的源代码：

public class QuestionBrute {

public static int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

public static boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) {
        return false;
    }
    else {
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

public static void main(String[] args) {
    // Create balanced tree
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    TreeNode root = TreeNode.createMinimalBST(array);
    System.out.println("Root? " + root.data);
    System.out.println("Is balanced? " + isBalanced(root));

    // Could be balanced, actually, but it's very unlikely...
    TreeNode unbalanced = new TreeNode(10);
    for (int i = 0; i < 10; i++) {
        unbalanced.insertInOrder(AssortedMethods.randomIntInRange(0, 100));
    }
    System.out.println("Root? " + unbalanced.data);
    System.out.println("Is balanced? " + isBalanced(unbalanced));
}
}

由于算法要检查每个节点的高度，并且我们没有在每次递归中保存高度，所以运行时间应该是 O(N^2)。

4

1 回答 1

4

首先，让我们修复一下您的代码。您检查根是否平衡的功能将无法正常工作，因为在以下情况下二叉树是平衡的：

maxHeight(root) - minHeight(root) <= 1

我引用维基百科：“平衡二叉树通常被定义为一个二叉树，其中每个节点的两个子树的深度相差 1 或更小”

您的算法将为这棵树给出错误的答案：

一个简单的二叉树，大小为 9，高度为 3，根节点的值为 2。上面的树是不平衡的，没有排序。

当你调用getHeight(Node7)它时它会返回 3，当你调用getHeight(Node5)它时它也会返回 3，因为(0>1) == false你会返回true:(

要解决此问题，您所要做的就是以int MinHeight(TreeNode node)与您相同的方式实施，getHeight()但使用Math.min()

现在回答你。就运行时复杂性而言，每当您getHeight()从根调用函数时，您正在执行DFS，并且由于您必须访问所有节点才能找到树的高度，因此该算法将为 O(N)。现在确实，您在调用时执行了该算法两次，maxHeight(root)但是minHeight(root)由于它们都是 O(N) （假设它们完全按照所做getHeight()的操作），因此总体复杂度将以 C*N 作为某个常数 C 的上限，并且所有N 大于某个 N 结，即 O(N)，其中 N 是树的节点数；）

干杯!

于 2013-01-30T05:08:48.853 回答