判断二叉树是否是平衡二叉树_判断给定的二叉树是否是平衡二叉树

二叉树的节点定义为

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6

二叉树的深度：根节点到叶节点的最长路径长度
平衡二叉树：二叉树中任一节点的左右子树的深度相差不超过1

递归的方法代码如下：

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;        
        }

        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if(Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right))
            return true;

        return false;
    } 

    public int getHeight(TreeNode node){
        if(node == null)
            return 0;
        int left = getHeight(node.left);
        int right = getHeight(node.right);

        return Math.max(left, right)+1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上述方法有很多的重复计算，性能不是很好。是否能实现每个节点只遍历一次呢，
可利用后序遍历的方法，在遍历每个节点的时候我们已经遍历了它的左右子树，且记录下其深度

import java.util.*;
public class Solution {    
     public boolean _IsBalanced_Solution(TreeNode root,int[] depth) {
         if(root == null){
             depth[0] = 0;
             return true;
         }
         int[] left = new int[1],right = new int[1];
         if(_IsBalanced_Solution(root.left,left) && _IsBalanced_Solution(root.right,right)){
             if(Math.abs(left[0] - right[0]) <= 1){
                 depth[0] = ((left[0] > right[0]) ? left[0] : right[0]) + 1;
                 return true;
             }
         }
         return false;
     }
    public boolean IsBalanced_Solution(TreeNode root) {
        int[] depth = new int[1];
        return _IsBalanced_Solution(root,depth); 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考：https://blog.csdn.net/xuchonghao/article/details/80351720