55.2 平衡二叉树

Leetcode

题目描述

平衡二叉树左右子树高度差不超过 1。

解题思路

后序遍历，自底向上计算每个节点的高度，同时检查它的左右子树高度差，发现不平衡就提前结束，时间复杂度 O(N)。如果自顶向下对每个节点调用一次求深度的函数再比较，同一个节点的高度会被它的每个祖先各计算一次。

private boolean isBalanced = true;

public boolean isBalanced(TreeNode root) {
    isBalanced = true;
    height(root);
    return isBalanced;
}

private int height(TreeNode root) {
    if (root == null || !isBalanced)
        return 0;
    int left = height(root.left);
    int right = height(root.right);
    if (Math.abs(left - right) > 1)
        isBalanced = false;
    return 1 + Math.max(left, right);
}