Получение ошибки stackoverflow при инвертировании двоичного дерева с использованием глобальной переменной

Question

Я пытаюсь инвертировать двоичное дерево, как в Java:

class Solution {
    TreeNode node;
    public TreeNode invertTree(TreeNode root) 
    {
        if(root == null)
            return null;

        node = root;

        node.left = invertTree(root.right);

        node.right = invertTree(root.left);

        return node;
    }
}

Однако при выполнении этого кода я получаю ошибку переполнения стека. Кто-нибудь может объяснить, почему?

Answer 1

Вам нужно создавать новые узлы и заменять их при разборе. Вы пытаетесь использовать один объект TreeNode для этого, поэтому вы никогда не достигнете своего базового условия.

Чтобы лучше понять, пожалуйста, используйте симпатичный метод печати и вызовите его из этого метода и наблюдайте за изменениями на небольшом вводе.

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

    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);

    root.left = right;
    root.right = left;

    return root;
}

Инверсия дерева с root r и поддеревьев справа и слева - это дерево с root r, правое поддерево которого является обратным левому, а левое поддерево - обратное справа.