【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;
        }
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容