p110

发表于 | 分类于 |

LeetCode p110 Balanced Binary Tree 题解

1.题目：

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.

2.解题思路:

dp

3.代码

[title] [] [url] [link text]
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
37
38
39
40
 
/**
 * 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 || (root.left == null && root.right == null))
			return true;
		if (dp(root) < 0)
			return false;
		else {
			return true;
		}

	}

	public int dp(TreeNode root) {

		if (root == null)
			return 0;
		int a = dp(root.left);
		int b = dp(root.right);
		if (a == -1 || b == -1) {
			return -1;
		}
		int l = a > b ? a - b : b - a;
		if (l > 1)
			return -1;
		else {
			return Math.max(a, b) + 1;
		}

	}
}

4.一些总结：