LeetCode 训练场:110. 平衡二叉树

简介: LeetCode 训练场:110. 平衡二叉树

1. 题目

110. 平衡二叉树


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 。


3. 实现方法

3.1 方法 1

3.1.1 思路

定义一个方法 depth() 来求二叉树的深度

先对二叉树进行判断是否为 null,是则说明该树是平衡树

若二叉树左右子树高度差大于 1,则说明该树不平衡

然后递归左右子树,判断是否均为平衡树

3.1.2 实现


public boolean isBalanced(TreeNode root) {
  // 判断根节点是否为 null,是则该树是平衡
    if (root == null) {
        return true;
    }
    // 若二叉树左右子树高度差大于 1,则说明该树不平衡
    if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
        return false;
    }
    // 递归左右子树,判断是否均为平衡树
    return isBalanced(root.left) && isBalanced(root.right);
}
// 求一个二叉树的深度
public int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + Math.max(depth(root.left), depth(root.right));
}
目录
相关文章
leetcode代码记录(平衡二叉树
leetcode代码记录(平衡二叉树
73 0
|
11月前
【LeetCode 33】110.平衡二叉树
【LeetCode 33】110.平衡二叉树
62 1
|
算法 Java 关系型数据库
leetcode110-平衡二叉树
文章通过LeetCode第110题"平衡二叉树"的解题过程,深入讲解了平衡二叉树的定义、树的高度概念,并提供了使用后序遍历算法判断二叉树是否平衡的Java代码实现,强调了理解理论知识和实践编码的重要性。
|
Python
【Leetcode刷题Python】110. 平衡二叉树
LeetCode第110题"平衡二叉树"的Python解决方案,通过计算二叉树的高度并判断任意两个子树的高度差是否不超过1来确定树是否平衡。
75 2
|
算法
【LeetCode题目详解】(五)144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历、104.二叉树的最大深度、110.平衡二叉树
【LeetCode题目详解】(五)144.二叉树的前序遍历、94.二叉树的中序遍历、145.二叉树的后序遍历、104.二叉树的最大深度、110.平衡二叉树
104 0
|
SQL 算法 数据挖掘
力扣110:平衡二叉树
力扣110:平衡二叉树
|
Java C++ Python
leetcode-110:平衡二叉树
leetcode-110:平衡二叉树
92 0
|
算法
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
代码随想录算法训练营第十七天 | LeetCode 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和
85 0