题解 | #判断是不是平衡二叉树#

跟上一题有点类似，如果用两层递归，时间复杂度太大。看了题解才发现可以边递归计算左右子树深度边判断是否平衡。可能平时不怎么用c++，竟然忘了引用这个功能。惭愧惭愧。。。

class Solution {
  public:
    bool judge(TreeNode* r, int& depth) {
        if (!r) return true;
        int left = 0, right = 0;//左右子树的深度
        if (!judge(r->left, left) ||
                !judge(r->right, right))return
                        false; //第一种情况，子树中就有非平衡的部分
        if (left - right > 1 ||
                right - left > 1) return
                        false; //第二种情况，子树都是平衡的，但本身不平衡

        depth = (left > right) ? left + 1 : right + 1;
        return true;
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        int depth = 0;
        return judge(pRoot, depth);
    }
};