110.Balanced Binary Tree---《剑指offer》面试39

题目大意：判断一个二叉树是否是平衡二叉树。

法一：dfs。利用求解二叉树的高度延伸，先计算左子树的高度，再计算右子树的高度，然后两者进行比较。o(nlgn)。代码如下（耗时4ms）：

 1     public boolean isBalanced(TreeNode root) {
 2         if(root == null) {
 3             return true;
 4         }
 5         //计算左子树高度
 6         int l = dfs(root.left);
 7         //计算右子树高度
 8         int r = dfs(root.right);
 9         //比较左子树和右子树高度
10         if(Math.abs(l - r) > 1) {
11             return false;
12         }
13         //如果左右子树有非平衡二叉树，则整体就是平衡二叉树，否则就不是
14         return isBalanced(root.left) && isBalanced(root.right);
15     }
16     //计算二叉树的高度
17     private int dfs(TreeNode root) {
18         if(root == null) {
19             return 0;
20         }
21         int l = dfs(root.left);
22         int r = dfs(root.right);
23         return (l > r) ? (l + 1) : (r + 1);
24     }

View Code

法二：dfs。每个结点只遍历一次，也就是边遍历，边记录其深度。o(n)。代码如下（耗时2ms）：

 1     public boolean isBalanced(TreeNode root) {
 2         return (dfs(root) == -1) ? false : true;
 3     }
 4     private int dfs(TreeNode root) {
 5         if(root == null) {
 6             return 0;
 7         }
 8         //记录左子树高度
 9         int l = dfs(root.left);
10         //如果左子树是非平衡树，则直接返回-1，不用进行下面的操作
11         if(l == -1) {
12             return -1;
13         }
14         //记录右子树高度
15         int r = dfs(root.right);
16         if(r == -1) {
17             return -1;
18         }
19         //比较左右子树的高度，如果是非平衡的，则返回-1
20         if(Math.abs(l - r) > 1) {
21             return -1;
22         }
23         //如果目前来说是平衡的，则返回当前平衡树的高度
24         else {
25             return 1 + Math.max(l, r);
26         }
27     }

View Code