平衡二叉树

本贴最后更新于 2231 天前,其中的信息可能已经物是人非

题目描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

解题思路

左右子树的深度差距小于等于一,且左右子树也是平衡二叉树。

  • 先判断整棵树,再判断子树。越底层的结点计算次数越多;

  • 先判断子树再判断整棵树,返回子树的深度,标志位放在函数体外。

代码

代码 1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        if (Math.abs(left-right) <= 1)
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        else
            return false;
    }
    
    private int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = TreeDepth(root.left)+1;
        int right = TreeDepth(root.right)+1;
        return Math.max((1 + TreeDepth(root.left)), (1 + TreeDepth(root.right)));
    }
}

代码 2

public class Solution {
    boolean ret = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return ret;
    }
    
    private int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = TreeDepth(root.left)+1;
        int right = TreeDepth(root.right)+1;
        if (Math.abs(left - right) > 1)
            ret = false;
        return Math.max(left, right);
    }
}

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...