LeetCode-110-平衡二叉树

题目

思路

1. 思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
2. 如果左右高度差≥2 ：则返回 -1，代表 此子树不是平衡树，然后接着向上返回 只有全都是平衡树 才会返回非-1的值

代码

    public boolean isBalanced(TreeNode root) {
    
        return recur(root) != -1;
    }

    //思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
    private int recur(TreeNode root) {
    
        //空指针返回0
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        //如果当前节点的左右子树的高度差<2 说明在当前节点算是平衡子树
        //返回以节点root为根节点的子树的最大高度，即节点 root 的左右子树中最大高度加 1
        //但如果左右高度差≥2 ：则返回 -1，代表 此子树不是平衡树，然后接着向上返回 只有全都是平衡树 才会返回非-1的值
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }