JZ39 平衡二叉树

2021年9月13日17:34:19
1.
剪枝
自底向上 不是平衡二叉树就返回-1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;

    }
    public int depth(TreeNode root){
        if(root == null) return 0;

        int left = depth(root.left);
        if(left == -1) return -1;

        int right = depth(root.right);
        if(right == -1) return -1;

        return Math.abs(left-right)<2 ?  Math.max(left,right)+1:-1;


    }
}

2.
自顶向上 计算量大

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;


        boolean left = IsBalanced_Solution(root.left);
        boolean right = IsBalanced_Solution(root.right);

        int ldepth = depth(root.left);
        int rdepth = depth(root.right);

        if(left && right && Math.abs(ldepth-rdepth) <=1) return true;
        else return false;
    }
    public int depth(TreeNode root){
        if(root == null) return 0;

        int left = depth(root.left);
        int right = depth(root.right);

        return Math.max(left,right) + 1;
    }
}