平衡二叉树

110. 平衡二叉树
题解:这道题目我走了一个误区,我以为的是平衡二叉树是只要保证根节点的左右子树高度之差在<=1,但是平衡二叉树是每个节点的左右子树高度之差都保证在<=1。所以我们的思路就是先递归每个节点,求出其左右子树的高度之差,如果不符合,则返回一个-1,表示此树已经不符合平衡二叉树,如果符合
则返回此节点的高度。

class Solution {

   public boolean isBalanced(TreeNode root) {
        return getHeight(root)>=0;
    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //递归,求出当前节点左右子树的高度
        int leftLength = getHeight(root.left);
        int rightLength = getHeight(root.right);
        //判断条件,如果符合则返回当前节点高度,否则返回-1,表示此树不是平衡二叉树
        if (Math.abs(leftLength - rightLength) > 1 || leftLength == -1 || rightLength == -1) {
            return -1;
        }
        return Math.max(leftLength, rightLength) + 1;
    }
}
上一篇:log4j2.x教程和实战


下一篇:ufw 简易防火墙设置