题解 | #平衡二叉树#

解法一、自上而下

这种解法每次都要去计算当前节点的高度，而计算高度的时候又要递归以当前节点为根的树，存在大量的重复计算。

import java.lang.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) > 1){
            return false;    
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return 1 + (leftHeight > rightHeight ? leftHeight :rightHeight);
    }
}

解法二、自下而上

从下至上进行计算，每次返回结果的同时带出自己的高度，从而避免了大量的重复计算。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        return bal(root, new int[1]);
    }   
    // 递归辅助函数， h是当前节点的高度，通过它可以返回给父节点自己的高度
    private boolean bal(TreeNode root, int[] h) {
        if (root == null) {
            h[0] = 0;
            return true;
        } else {
            int[] l = new int[1];
            int[] r = new int[1];
            if (!bal(root.left, l) || !bal(root.right, r)) {
                h[0] = l[0] > r[0] ? l[0] + 1 : r[0] + 1;
                return false;
            } else if (l[0] - r[0] > 1 || r[0] - l[0] > 1) {
                h[0] = l[0] > r[0] ? l[0] + 1 : r[0] + 1;
                return false;
            } else {
                h[0] = l[0] > r[0] ? l[0] + 1 : r[0] + 1;
                return true;
            }
        }
    }
}