怎样分析这个算法的时间/空间复杂度？

Question

下面代码是判断一个二叉树是否是平衡二叉树，以这段代码所表达的算法为例，怎样去衡量他的时间/空间复杂度？（每到一个节点都去求他的深度，这样对于时间复杂度来说是不是太高了？）
PS:如果有更好的方法，Please show me your code^_^

class Solution {
public:
    bool isBalanced(TreeNode *root) {
      if(root==NULL)
         return true;
      if(abs(maxDepth(root->left)-maxDepth(root->right))>1)
         return false;
      else
         return (isBalanced(root->left))&&(isBalanced(root->right));
    }
    int maxDepth(TreeNode *root)
    {
        if(root==NULL)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }


};

Answer 1

时间复杂度上我看是 O(n log n)。比如你拿到一个完全二叉树，那么最底层的每一个节点你都会访问 log n 次。

方法肯定是不好的。对于同一个 subtree 的高度你会去求很多次。存在 O(n) 的方法。

随手改一个也不怎么好的

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return maxDepth(root) >= 0;
    }
    int maxDepth(TreeNode *root) {
        if (root == NULL) { return 0; }
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        if (left < 0 || right < 0 || abs(left - right) > 1) {
            return -1;
        } else {
            return max(left, right) + 1;
        }
    }
};