Предварительное увеличение рекурсивного вызова

Question

Я решал этот вопрос с кодом leetcode https://leetcode.com/problems/binary-tree-right-side-view/description/.

Следующий код работает правильно.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List <Integer> ans = new LinkedList<>();
        if (root == null) return ans;
        traverse(root, ans, 0);
        return ans;
    }

    public void traverse(TreeNode root, List<Integer> ans, int currDepth){
        if (root == null) return;

        if (ans.size() == currDepth) ans.add(root.val);
        traverse(root.right, ans, currDepth + 1);
        traverse(root.left, ans, currDepth + 1);
    }
}

Однако во время последних 2 рекурсивных вызовов, если я изменюстрок на

 traverse(root.right, ans, ++currDepth);
 traverse(root.left, ans, ++currDepth);

код не работает, почему это происходит?Разве обе версии не должны быть эквивалентными?

Answer 1

Допустим, currDepth = 0

В вашей первой версии два рекурсивных вызова будут выглядеть следующим образом:

traverse(root.right, ans, 1);
traverse(root.left, ans, 1);

Это правильно, потому что вы хотите, чтобы оба рекурсивных вызова перешли наследующий уровень.

В вашей второй версии это выглядит следующим образом:

traverse(root.right, ans, 1);
traverse(root.left, ans, 2);

Это означает, что первый рекурсивный вызов работает нормально, но второй неверен (пропускает один уровень).

Почему?Вы изменили ваш currDepth параметр.Первая версия вашего кода не меняет его.Проходит currDepth + 1 на следующий уровень.