剑指Offer:平衡二叉树

题目

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

分析

根据题目要求我们可以选择用后序遍历方法来遍历二叉树,因为使用后序遍历方法,再遍历到一个节点之前,我们就已经遍历了它的左右子树。只要再遍历每个节点的时候记录他的深度,我们就可以一边遍历,一边判断每个节点是否是平衡的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}

int left = TreeDepth(root.left);
int right = TreeDepth(root.right);

return (left > right) ? left+1 : right+1;
}

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