长大后想做什么？做回小孩！

0%

LeetCode——平衡二叉树

发表于 分类于 Valine：
本文字数： 125

NO.110 平衡二叉树 简单

JFdJdx.png

思路一：递归实现 只需要判断是否是高度平衡二叉树即可。

NO.104 二叉树的最大深度的升级版，分别计算根节点的左右子树的最大深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
boolean isBBT = true;

public boolean isBalanced(TreeNode root) {
    dfs(root);
    return isBBT;
}

private int dfs(TreeNode root) {
    if (root == null) return 0;
    //左右子树深度
    int left = dfs(root.left) + 1;
    int right = dfs(root.right) + 1;
    //高度不平衡，false
    if (Math.abs(left - right) > 1) isBBT = false;
    //左右子树最大深度
    return Math.max(left, right);
}

时间复杂度：O(n) 深度优先遍历一次

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github