剑指offer 39 平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

class Solution {
    //后续遍历二叉树，遍历过程中求子树高度，判断是否平衡
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
		int dep=0;
        return IsBalanced(pRoot,dep);
    }
    
    bool IsBalanced(TreeNode *root,int &dep){
        if(root==NULL){
            return true;
        }
        
        int leftlen=0,rightlen=0;
        
        if(IsBalanced(root->left,leftlen)&&IsBalanced(root->right,rightlen)){
            int dif=leftlen-rightlen;
            if(dif<-1||dif>1){
                return false;
            }
            
            dep =(leftlen>rightlen?leftlen:rightlen)+1;
            return true;
        }
        return false;
    }
};