Максимальная глубина бинарного дерева

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 (для корня).

Answer 2

Трудно представить, что вы столкнетесь с проблемой большинства бинарных деревьев, если только:

• это действительно большое (и / или вырожденное) двоичное дерево; или же
• он не структурирован правильно (например, имеет круговую петлю в структуре); или же
• ваш лимит времени очень маленький.

Так что это будет первое, что я проверю.

Однако в вашем случае это возможно потому, что вы вызываете функцию рекурсивно гораздо чаще, чем вам нужно.

Имея два вызова функции глубины в вашем коде для каждого поддерева (один для сравнения глубин и один для возврата самого глубокого поддерева), вы значительно увеличиваете рабочую нагрузку. Было бы лучше кэшировать длины, чтобы вы могли их повторно использовать, что-то вроде (псевдокод):

def maxDepth(nd):
    if nd == null:               # Empty-sub-tree depth is zero.
        return 0

    deepest = maxdepth(nd.left)  # Initially assume left is deepest.

    dright = maxdepth(nd.right)  # Or use right if deeper.
    if dright > deepest:
        deepest = dright

    return 1 + deepest           # Depth: this node plus deepest sub-tree.