剑指offer-39-平衡二叉树

思路

平衡二叉树的定义，空树或者两颗子树的高度差小于等于1，注意一定是子树的高度差。

代码

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){return true;}
        int h1=TreeDepth(root.left);//一定是子树的高度差
        int h2=TreeDepth(root.right);
        if(Math.abs(h1-h2)>1){
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }


    public int TreeDepth(TreeNode root) {
        if(root==null){return 0;}
        return 1+Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }
}