美文网首页刷爆力扣
【24】平衡二叉树

【24】平衡二叉树

作者: 公孙剑人 | 来源:发表于2021-05-16 11:53 被阅读0次

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/balanced-binary-tree/

题目

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

本题中,一棵高度平衡二叉树定义为:
    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:



输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:



输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例3:
输入:root = []
输出:true

  • 提示:
    • 树中的节点数在范围 [0, 5000] 内
    • -104 <= Node.val <= 104

思路

要判断左右节点高度是否相差1,可以从子节点开始递归,自底向上比较左右节点的高度。

代码

    public boolean isBalanced(TreeNode root) {
        // -1表示高度相差超过1
        return recursive(root) != -1;
    }

    /**
     * 自底向上遍历二叉树
     * @param node
     * @return
     */
    private int recursive(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = recursive(node.left);
        if (left == -1) {
            return -1;
        }
        int right = recursive(node.right);
        if (right == -1) {
            return -1;
        }
        // 取最大高度+1,否则,返回-1,表示当前两节点高度相差超过了1
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }

结果

执行结果

相关文章

  • 剑指 offer:39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路: 平衡二叉树:Wiki:在...

  • 平衡二叉树

    1)什么是平衡二叉树?2)平衡二叉树的特点是什么?3)平衡二叉树的构建实现? 一、什么是平衡二叉树?假设有一组数据...

  • 面试题:平衡二叉树

    题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 知识点 平衡二叉树 Qiang的思路 平衡二叉树是指一个...

  • Leetcode 110 平衡二叉树

    平衡二叉树 题目 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每...

  • 二叉树2-平衡二叉树、完全二叉树、二叉树剪枝

    110.平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 一棵高度平衡二叉树定义为:一个二叉树每个节点 ...

  • Leetcode题解 - Easy - 4

    110- 平衡二叉树 问题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一...

  • TreeMap源码分析

    TreeMap 平衡二叉树 平衡二叉树(Self-balancing binary search tree)又被称...

  • 图的应用[平衡二叉树以及散列查找]

    平衡⼆二叉树( AVL 树) 平衡⼆二叉树(Self-Balancing Binary Search Tree 或...

  • [LeetCode]110. 平衡二叉树

    110. 平衡二叉树给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个...

  • 力扣算法 - 平衡二叉树

    平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的...

网友评论

    本文标题:【24】平衡二叉树

    本文链接:https://www.haomeiwen.com/subject/wznljltx.html