平衡二叉树

题意

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过 1。

样例

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

二叉树 A 是高度平衡的二叉树,但是 B 不是。

思路

这道题利用了 二叉树的最大深度 这个问题,就是求每一个左右节点的深度,如果两个深度之间的差大于 1,则说明该树不是一个平衡二叉树,该算法只会将所有元素遍历一次。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean IsBalanced_Solution(TreeNode root) {
return Height(root) != -1;
}

public int Height(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = Height(node.left);
if (leftDepth == -1) {
return -1;
}

int rightDepth = Height(node.right);
if (rightDepth == -1) {
return -1;
}

if (Math.abs(leftDepth - rightDepth) > 1) {
return -1;
}

return Math.max(leftDepth, rightDepth) + 1;
}

原题地址

牛客网:平衡二叉树

坚持原创技术分享,您的支持将鼓励我继续创作!