平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路

深度搜索，剪枝。
时间复杂度O(lgn)，空间复杂度O(lgn)。

未剪枝代码

public class Solution {
    private int depth(TreeNode root) {
        return root == null ? 0 : Math.max(1+depth(root.left), 1+depth(root.right));
    }
    
    public boolean IsBalanced_Solution(TreeNode root) {
        return root == null ? true : Math.abs(depth(root.left) - depth(root.right)) <= 1;
    }
}

剪枝代码

public class Solution {
    private 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 ? 1 + Math.max(left, right) : -1;
    }
    
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }
}