导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-110.Balanced Binary Tree

题目

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

翻译

给出一颗二叉树,判断其是否是高度平衡的。
对于本题,对于一颗二叉树的每个节点,其左右子树的高度差都不超过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
25
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root ==null)
return true;
if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1)
return false;
return isBalanced(root.left) && isBalanced(root.right);
}

public int getDepth(TreeNode root) {
if (root == null)
return 0;

return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
}

过程中在遍历每个节点判断是否平衡树中,重复计算了各个子节点的深度,因此可以维护一个map,记录每个节点的深度,优化算法:

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private Map<TreeNode, Integer> depthMap = new HashMap<TreeNode, Integer>();

public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1)
return false;
return isBalanced(root.left) && isBalanced(root.right);
}

public int getDepth(TreeNode root) {
if (root == null)
return 0;
if (!depthMap.containsKey(root)) {
int height = Math.max(getDepth(root.left), getDepth(root.right)) + 1;
depthMap.put(root, height);
}

return depthMap.get(root);
}
}

另外一种算法,在计算节点深度的同时,判断以该节点为根的子树是否是平衡二叉树,省去了判断每颗子树是否是平衡二叉树的递归过程:

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
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
return getDepth(root) != -1;
}

// 用-1标注以该节点为根的子树不是平衡二叉树
// (左子树不为平衡二叉树或右子树不为平衡二叉树或左右子树深度差大于1)
// 否则返回深度
public int getDepth(TreeNode root) {
if (root == null)
return 0;

int leftDepth = getDepth(root.left);
if (leftDepth == -1)
return -1;

int rightDepth = getDepth(root.right);
if (rightDepth == -1)
return -1;

int diff = Math.abs(leftDepth - rightDepth);
if (diff > 1)
return -1;

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

另外,在《Cracking the code interview》中有一道题,判断一颗二叉树是否平衡,其对平衡的定义是树中不存在深度差大于1的叶子节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isBalanced(TreeNode root) {
return getMaxDepth(root) - getMinDepth(root) <= 1;
}

public int getMaxDepth(TreeNode root) {
if (root == null)
return 0;

return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
}

public int getMinDepth(TreeNode root) {
if (root == null)
return 0;

return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;
}

参考:
http://www.algoqueue.com/algoqueue/default/view/8912896/check-binary-tree-balanced-or-not
Gayle Laakmann. Cracking the Coding Interview, Fourth Edition[M]. CreateSpace, 2008-10-15.