【1错-1】是否平衡二叉树

https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

日期	是否一次通过	comment
2019-01-27 20:20	N	1. 对maxDepth理解不深：maxDepth是不停的分治，判断左右子树最大深度（postOrder），而不是累加；2. maxDepth在本题中复杂度太高，相当于每个子树都得算独立的深度，不科学

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

1. 原版maxDepth

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) {
            return true;
        }
         
       if(Math.abs(helper(root.left) - helper(root.right)) > 1) {
           return false;
       }
       return true;
    }
     
    private int helper(TreeNode root) {
        if(root == null) {
            return 0;
        }
         
        return Math.max(helper(root.left), helper(root.right)) + 1;
    }
}

2. 调整后的maxDepth

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return helper(root) != -1;
    }
    
    private int helper(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftDpt = helper(root.left);
        int rightDpt = helper(root.right);
        if(leftDpt == -1 || rightDpt == -1 || Math.abs(leftDpt - rightDpt) > 1) {
            return -1;
        }
        
        return Math.max(leftDpt, rightDpt) + 1;
    }
}