判断是不是平衡二叉树_

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围： $n \le 100$ ,树上节点的val值满足 $0 \le n \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

牛客题解官

发表于 2020-06-01 15:02:46

精华题解题解这是一篇针对初学者的题解，用两种方法解决。知识点：树，递归难度：一星题解方法一：自顶向下判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。根据定义，如果我们能够求出以每个结点为根的树的高度，然后再根据左展开全文

LaN666

发表于 2021-06-23 10:06:49

精华题解 39、平衡二叉树解题思路：这道题目其实跟二叉树的深度这道题用到的方法是一样的，为什么说是一样的呢？因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值，但是这道题目是要让我们判断二叉树是不是平衡树。我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的展开全文

牛客题解官

发表于 2022-04-22 12:06:57

精华题解题目主要信息：判断给出的二叉树是否是平衡二叉树需要判断任意一节点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则举一反三：学习完本题的思路你可以解决如下题目： BM28. 二叉树的最大深度 BM29. 二叉树中和为某一值的路径（一） BM31. 对称的二叉树 BM32 展开全文

ajaj

发表于 2021-07-18 15:12:04

精华题解思路: 从题中给出的有效信息：左右两个子树的高度差的绝对值不超过1 左右两个子树都是一棵平衡二叉树故此首先想到的方法是使用递归的方式判断子节点的状态方法一：dfs 具体做法：如果一个节点的左右子节点都是平衡的，并且左右子节点的深度差不超过 1，则可以确定这个节点就是一颗平衡二叉树。具体过展开全文

牛客786963925号

发表于 2021-07-12 22:20:39

精华题解解法一：自顶向下一棵二叉树为「平衡二叉树」的条件为：该树为空树，或者其左右子树的高度差最大为1。因此，判断一棵二叉树是否平衡需要求其子树高度，并比较左右子树高度差。因此此题的解题步骤如下：设计「求二叉树高度」的函数getHeight(root)，作用是求以root为根结点的二叉树高度；遍历展开全文

江南好___

发表于 2021-06-22 19:03:23

精华题解描述题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。注：我们约展开全文

NumPy

发表于 2021-06-22 20:12:50

精华题解一、题目描述题目大意：输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。注：我们展开全文

一叶浮尘

发表于 2019-08-23 12:56:15

输入一棵二叉树，判断该二叉树是否是平衡二叉树。之前是因为自己对平衡二叉树对定义不是很清楚：平衡二叉树的左右子树也是平衡二叉树，那么所谓平衡就是左右子树的高度差不超过1. public class Solution { public int depth(TreeNode root){ 展开全文

牛客153595411号

发表于 2020-02-12 09:58:59

平衡二叉树的定义是左右子树高度差不超过1，同时左右子树也是平衡二叉树，于是代码逻辑可以如下1.判断树是否为空，空则返回true2.判断左右子树深度差，其中，求树深度的函数在上一题中“二叉树的深度中”已实现，差超过1，返回false3.若通过2的判断，对左右子树也判断是否都是平衡二叉树，判断函数为函数展开全文

桐乐

发表于 2019-12-27 15:22:42

平衡二叉树定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。思路：根据定义，我们只需要后序遍历此树，从树的叶子节点开始计算高度，只要有一个子树不满足定义就返回-1，如果满足继续向上计算高度。 class Solution { public: b 展开全文

Ironxin

发表于 2020-03-10 13:24:21

首先搞清楚意思，本题的重点在于树是否平衡，左右子树的深度不超过1。而不关注于是否将其排序，成为平衡二叉搜索树。因此在只考虑平衡的情况下解题。思路1：（由二叉树的深度的解法转换过来（55-1题就是求二叉树深度））在使用递归求的深度后，其实可以在递归中，直接判断左右子树的差值。这时候就相当于多一个变量展开全文

张田懿

发表于 2020-12-08 18:48:20

-- coding:utf-8 -- class TreeNode: def init(self, x): self.val = x self.left = None self.right = None class Solution: def IsBalanced_Solution(self, 展开全文

渣渣华华

发表于 2020-05-28 16:20:31

在获得左右子树高度后进行差值判断，若出现高度差大于1的情况，改变flag标志唯一注意的是：空树也是平衡二叉树 public class Solution { boolean flag = true; public boolean IsBalanced_Solution(TreeNod 展开全文

摸鱼学大师

发表于 2021-10-03 19:56:35

题目的主要信息：判断给定的一棵树是否是平衡二叉树平衡二叉树：：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树方法一：自顶向下求深度具体做法：递归遍历二叉树的每个结点，再递归计算每个结点的左右子树深度，判断每个结点的是否满足平衡二叉树的要求。展开全文

橙子爱吃桃子

发表于 2020-06-25 15:57:48

C++简洁代码（2行）： class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { return !pRoot ? true : abs(depth(pRoot->left) - depth 展开全文

小洋芋热爱NLP

发表于 2020-11-27 19:48:16

- 题目描述： - 题目链接： https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=188&&tqId=36580&rp=1&ru=/ta/job-code-high-wee 展开全文

牛客最菜男人

发表于 2020-04-02 18:30:03

双重递归（利用上一题的结果） public class Solution { public int TreeDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(TreeD 展开全文

判断是不是平衡二叉树

输入描述:

输出描述:

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题