平衡二叉樹的檢查

/**
 *實作一個函數，檢查二叉樹是否平衡，平衡的定義如下，對于樹中的任意一個結點，其兩顆子樹的高度差不
 * 超過1。
 * 給定指向樹根結點的指針TreeNode* root，請傳回一個bool，代表這棵樹是否平衡。
 */
           

import java.util.*;


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Balance {
    /**
     * 解決方法是使用遞歸，将問題單一化；
     * 将問題簡單化為隻需要求出左子樹，右子樹的高度，檢查兩者的差是否大于1
     * 在求子樹高度時需要使用遞歸求解；同時也需要對根節點的周遊求解進行遞歸,判斷是否每個節點都滿足平衡
     * 隻有所有節點都滿足平衡才說明此樹是一個平衡樹
     *
     * @param root
     * @return
     */
    public boolean isBalance(TreeNode root) {

        if (root == null)
            return true;

        //擷取左子樹的高度
        int leftHeight = getHeight(root.left);
        //擷取右子樹的高度
        int righHeight = getHeight(root.right);
        //abs()傳回絕對值
        if (Math.abs(leftHeight - righHeight) > 1){
            return false;
        }
		//對樹節點進行周遊，判斷是否所有節點都滿足平衡
        return isBalance(root.left) && isBalance(root.right);
    }

	//求出子樹的高度
    private int getHeight(TreeNode node){
        if (node == null)
            return 0;
        return Math.max(getHeight(node.left),getHeight(node.right)) + 1;
    }
}