蓝桥杯刷题JAVA（6）

1.平衡二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getdeepth(root) != -1;
    }

    public int getdeepth(TreeNode root){
        if(root == null)
            return 0;
        int right = getdeepth(root.right);
        int left = getdeepth(root.left);
        if(right == -1 || left == -1)
            return -1;
        if(Math.abs(left - right) > 1)
            return -1;
        else
            return Math.max(left, right) + 1;
    }

}

经验： （1）DP的经验不足，depth事实上是从null节点开始返回比较好， （2）刷题的时候关注的永远是最后结果，事实上是否求出depth是不重要的，只要找到不平衡的地方就可以直接无限返回-1直至函数出栈。

2.二叉树的最小深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        if(root.right == null && root.left != null)
            return 1 + minDepth(root.left);
        if(root.right != null && root.left == null)
            return 1 + minDepth(root.right);
        return  Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

经验： 此题非常容易出现审题错误，认为只是最大深度的翻版，事实上，对于有一边为空的树那一边是不能够算作叶子节点的，直接使用最小深度容易算错。好题！！

3.路径总和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null)
            return false;
        if(root.right == null && root.left == null)
            if(targetSum - root.val == 0)
                return true;
            else
                return false;
        else
            return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
        
    }
}

经验： （1）关于JAVA常常会出现的空指针异常（NullPointerException），基本上是由于类变量为null时调用其成员变量导致的错误，需要利用if判断排除掉null的可能性。 4.杨辉三角

class Solution {
    public List generate(int numRows) {
        List result = new ArrayList();
        for(int i = 0; i