写在前面

剑指offer：平衡二叉树

题目要求

输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。

解法

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(!pRoot) return true;
        bool res = true;
        helper(pRoot,res);
        return res;
    }

    int helper(TreeNode* pRoot,bool& res) {
        if(!pRoot) return 0;
        int l = helper(pRoot->left,res) + 1;
        int r = helper(pRoot->right,res) + 1;
        if(abs(l-r)>1)
            res = false;
        return max(l,r);
    }
};

分析：递归求解左右字数的高度比较二者的差的绝对值如果大于1，标识量res置为false否则为true。