Пространственная сложность алгоритма дерева dfs

Question

Я оцениваю сложность пространства следующего алгоритма для инвертирования дерева:

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

Я знаю, что сложность пространства - это количество раз, которое вызывается стеком вызовов, которое равно O (h ) где h - высота дерева. Но я путаюсь с тем, что на каждом уровне стека вызовов мы возвращаем дерево, которое занимает некоторое пространство, почему мы не считаем это пространство? Я думаю, это потому, что дерево передается функцией. Но как вы учитываете это пространство? Java передается по ссылке, сколько места занимает ссылка на каждом уровне стека вызовов?

Answer 1

Пространство, необходимое для ссылки на объект, является постоянным. Это не зависит от того, на что вы ссылаетесь. Пространство, необходимое для ссылки на root дерева, такое же, как пространство, необходимое для ссылки на лист.

В общем случае можно предположить, что каждый вызов метода в Java принимает такое же количество места в стеке. Нет возможности выделить память в стеке (или, по крайней мере, пока). В этом методе никакие объекты не создаются и не уничтожаются в куче, поэтому используется только пространство для кадров стека.