劍指offer-JZ39-平衡二叉樹

題目描述

輸入一棵二叉樹，判斷該二叉樹是不是平衡二叉樹。code

在這裏，咱們只須要考慮其平衡性，不須要考慮其是否是排序二叉樹排序

思路：

遞歸思想，先計算左子樹深度，再計算右子樹深度，若是兩子樹深度相差大於1則返回-1，不然返回二者之間較大者+1遞歸

C++io

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return IsBalanced(pRoot) >= 0;
    }
    int IsBalanced(TreeNode* pRoot){
        if(pRoot == nullptr)
            return 0;
        int left = IsBalanced(pRoot->left);
        int right = IsBalanced(pRoot->right);
        int delta = abs(left - right);
        if(delta <= 1 && left >= 0 && right >= 0)
            return max(left, right) +1;
        else
            return -1;
    }
};