java - 二叉树的最大深度

Question

public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        else
        return (maxDepth(root.left)>maxDepth(root.right))?(maxDepth(root.left)+1):(maxDepth(root.right)+1);
    }
}

它返回超出时间限制。我想知道为什么会发生这种情况，我的代码有什么问题吗？

Answer 1

你们真的很接近。我认为您的目标是:

int maxHeight(TreeNode p) {
  if (p == null) return 0;
  int leftHeight = maxHeight(p.left);
  int rightHeight = maxHeight(p.right);
  return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

我认为您超过时间限制的原因是因为您的递归调用比您需要的要多得多。为了解决这个问题，你只需要计算左子树的大小，右子树的大小，并返回两个值中较大的一个+1(对于根)。