给定一个二叉树,判断它是否是高度平衡的二叉树。
发布日期:2021-10-06 02:38:33 浏览次数:1 分类:技术文章

本文共 797 字,大约阅读时间需要 2 分钟。

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3   / \  9  20
/  \   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1
  / \
 2   2
/ \   3   3  / \ 4   4

返回 false 。

/**

 * 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) {

        if(root == null) return true;

        int left = getHight(root.left);

        int right = getHight(root.right);

        if(Math.abs(left-right) > 1 ) return false;

        return isBalanced(root.left) && isBalanced(root.right) ;

    }

 

    private int getHight(TreeNode t){

        if(t == null) return 0;

        int left = getHight(t.left);

        int right = getHight(t.right);

        return Math.max(left,right)+1;

    }

}

 

 

 

转载地址:https://blog.csdn.net/luxuiary/article/details/106146261 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:synchronized 不是万能,错误加锁
下一篇:老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。

发表评论

最新留言

感谢大佬
[***.36.149.40]2022年07月30日 10时39分43秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章