java - 难以理解为什么在尝试反转二叉树时必须创建一个新的临时 TreeNode

Question

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

我不明白为什么上面的解决方案有效，但下面的解决方案却不起作用。

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

有人可以详细说明一下为什么必须有一个临时的 TreeNode 才能使程序运行吗？

Answer 1

首先，第一个代码片段不会创建新的TreeNode。它只存储对根的原始左子节点的引用。

如果您不保留该引用(如第二个代码段中所示)，则会丢失对根的原始左子树的引用，因为您将反转右子树的结果分配给 root.left(在 root.left = invertTree(root.right); 中)，因此 invertTree(root.left) 不会对根的原始左子树进行操作。

另一种看待它的方式 - 临时变量的原因类似于需要临时变量来交换两个变量的原因。