leetcode110.平衡二叉树,111.二叉树的最小深度

平衡二叉树

题目链接

题解：递归

什么是平衡二叉树？
平衡二叉树对任意一个节点来说，左子树与右子树的高度差不会超过1
例如：

对该树而言，这棵树的任意一个节点的左子树和右子树的高度差不大于1，所以这棵树是一棵平很二叉树。
本题需要判断一棵树是否为平衡二叉树，解题思路如下：

如果这棵树是一棵平衡二叉树，那么对任意一个节点来讲
1.左子树是一棵平衡二叉树
2.右子树是一棵平衡二叉树
3.左子树和右子树的高度差小于等于1

本题从宏观的角度去思考，应用了递归的思想，代码如下：

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

    public static class BalancedHeight{
        // 规定规定balancedHeight为-1的时候 二叉树不是平衡二叉树
        public int balancedHeight;
        public BalancedHeight(int h){
            this.balancedHeight = h;
        }
    }

    private BalancedHeight getBalancedHeight(TreeNode node){
        if(node == null){
            return new BalancedHeight(0);
        }

        int leftHeight = getBalancedHeight(node.left).balancedHeight;
        int rightHeight = getBalancedHeight(node.right).balancedHeight;
        if(leftHeight == -1){
            return new BalancedHeight(-1);
        }
        if(rightHeight == -1){
            return new BalancedHeight(-1);
        }
        if(Math.abs(leftHeight - rightHeight) > 1){
            return new BalancedHeight(-1);
        }

        return new BalancedHeight(Math.max(leftHeight,rightHeight) + 1);
    } 
}

时间复杂度：因为本思路需要遍历二叉树的每一个节点，所以时间复杂度为O(N)
额外空间复杂度：当二叉树极度不平衡时，递归的深度为N，所以额外空间复杂度为O(N)

执行结果：

二叉树的最小深度

题目链接

题解：递归

本题和二叉树的最大深度思路一致，在这里就不赘述了~

代码如下：

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

时间复杂度：O(N)
额外空间复杂度：当树极度不平衡，每个节点都只有一个孩子，递归会调用N次，栈空间的开销为N,所以额外空间复杂度为O(N)

执行结果：