110. Balanced Binary Tree

发表于 | 分类于 | 阅读次数:
字数统计: 248 | 阅读时长 ≈ 1

平衡二叉树

参考剑指Offer(55) 题目二 平衡二叉树判定的思路。

LeetCode 110 英文版
LeetCode 110 中文版

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @description: leetcode 110
 * @author: rhsphere
 * @since: 2019-08-29 01:08 by jdk 1.8
 */
public class BalancedBinaryTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isBalanced(TreeNode root) {
        return getDepth(root) != -1;
    }
    private int getDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = getDepth(root.left);
        if (left == -1)
            return -1;
        int right = getDepth(root.right);
        if (right == -1)
            return -1;
        return Math.abs(left - right) > 1 ? -1 : Math.max(left + 1, right + 1);
    }
}

题目

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 。

0%