即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

平衡二叉树(java版)

编程语言 ouyangyanlan 76℃ 0评论

【题目描述】输入一棵二叉树,判断该二叉树是否是平衡二叉树。

注:注意平衡二叉树和平衡二叉搜索树的区分。有的书中混淆了两个概念。这里的平衡二叉树只关注是否平衡。


【解题思路】


//1. 平衡二叉树的定义是,满足任何一个节点的左右子树高度差都不大于1


//2. 递归处理。先判断根节点是否满足左右子树高度差的关系。然后判断左子树是否满足平衡二叉树的定义,然后是判断右子树。只有所有的节点都满足平衡二叉树的定义,则该树为平衡二叉树。


//3. 当前节点的高度也是一个递归的值,为其左子树和右子树高度中的最大值+1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        boolean flag=false;
        if(root !=null){
            int depthDiff = Math.abs(getDepth(root.left)-getDepth(root.right));
            if(depthDiff <= 1){
                flag = true;
            }
            flag = flag && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }else{
            flag = true;
        }
        return flag;
    }

    //求当前节点的高度
    public int getDepth(TreeNode root){
        int max = 0;
        if(root != null){
            max = Math.max(getDepth(root.left), getDepth(root.right))+1;
        }
        return max;
    }
}

转载请注明:CodingBlog » 平衡二叉树(java版)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情