Сложность времени для данной задачи рекурсии дерева

Question

Я искал первое рекурсивное решение для этой проблемы в Leetcode.Вот код для предложенного решения.

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
}

Часть решения, которую я не понимаю, - это то, почему автор решения говорит, что сложность времени равна O (n).Допустим, у меня был ввод:

   1
  / \
 2   2

Вот как я отслеживаю стек вызовов в этом случае:

isMirror(1, 1)
    (t1.val == t2.val) returns true
    isMirror(2, 2) returns true
        (t1.val == t2.val) returns true
        isMirror(null, null) return true
        isMirror(null, null) return true
    isMirror(2, 2) returns true
        (t1.val == t2.val) returns true
        isMirror(null, null) return true
        isMirror(null, null) return true

В приведенном выше стеке вызовов isMirror () вызывается 7 разв то время как n равно 3. Чтобы временная сложность была O (n), должен ли isMirror () вызываться только 3 раза?Или я смотрю на это неправильно?Является ли тот факт, что стек вызовов прошел только на 3 уровня, показывает, что сложность времени составляет O (n)?

Спасибо за помощь.

Answer 1

Вы также вызываете зеркало на нулевых узлах.Таким образом, ваши элементы на самом деле не 3, а 7. Подумайте о следующем уровне двоичного дерева, и вы увидите.

Решения;

• Попробуйте проверить нулевое значение перед вызовом функции..
• это будет постоянным фактором для вашей стоимости.Примерно в 2 раза.По большим правилам O вы все еще O (n).