劍指Offer 平衡二叉樹

題目：輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹。

方法一：最直接的做法，周遊每個結點，借助一個擷取樹深度的遞歸函數，根據該結點的左右子樹高度差判斷是否平衡，然後遞歸地對左右子樹進行判斷。但是這種方法需要重複周遊節點多次。

class Solution {
public:
    int getHeight(TreeNode* pRoot){
        if(pRoot == nullptr)
            return 0;
        return max(getHeight(pRoot->left),getHeight(pRoot->right))+1;
    }
    int diff(TreeNode* pRoot){
        if(pRoot == nullptr)
            return 0;
        return getHeight(pRoot->left)-getHeight(pRoot->right);
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return true;
        int v = diff(pRoot);
        if(v<-1 || v>1)
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
    }
};
           

方法二：不需要重複周遊節點多次。通過後續周遊時，周遊到一個節點，其左右子樹已經周遊,依次自底向上判斷，每個節點隻需要周遊一次。

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return true;
        IsAvlTree = true;
        getHeight(pRoot);
        return IsAvlTree;
    }
     int getHeight(TreeNode* pRoot){
        if(pRoot == nullptr)
            return 0;
        int left = getHeight(pRoot->left);
        int right = getHeight(pRoot->right);
        if(abs(left-right)>1)
            IsAvlTree = false;
        return max(left,right)+1;
    }
private:
    bool IsAvlTree;
};