【D3】平衡二叉树 & 二叉树的最小深度 (LC 110&111

110. 平衡二叉树

问题描述

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

解题思路 1

首先，计算左右子树的最大深度，如果左右子树的高度差是否不超过 1，则该节点的左右子树高度平衡；
然后，再分别递归地遍历左右子节点，分别判断除根节点外的每个节点的左子树和右子树是否平衡。

代码实现 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) {
        if(root == null){
            return true;
        }
        return Math.abs(getDepth(root.left) - getDepth(root.right)) > 1 ? false : true 
                && isBalanced(root.left) && isBalanced(root.right); 
    }
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
}

解题思路 2

上一种方法中计算二叉树深度的函数会被重复调用。其实，在计算二叉树深度时即可以判断节点的左右子树是否平衡。定义返回值-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 boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return getDepth(root) >= 0;
    }
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftDepth = getDepth(root.left);
        if(leftDepth == -1 ){
            return -1;
        }

        int rightDepth = getDepth(root.right);
        if(rightDepth == -1 ){
            return -1;
        }
        
        return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth, rightDepth) + 1;
    }
}

111. 二叉树的最小深度

问题描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

解题思路

递归求出左右子树的最小深度，然后返回较小的值。
注意：当左/右子树二者有且仅有一者为空时，空子树的minDepth为0。但由于空子树没有叶子节点，所以即使0是较小的值，也应该返回非空子树的minDepth。

代码实现

/**
 * 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.left == null && root.right == null){
            return 1;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(left == 0){
            //左子树为空
            return right + 1;
        }else if(right == 0){
            //右子树为空
            return left + 1;
        }else{
            //左、右子树均不为空
            return left < right ? left + 1 : right + 1;
        }
    }
}