无法理解为什么在尝试反转二叉树时必须创建新的临时 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

在第二次分配后，您将 root.right 分配给 root.left，但上一行将 root.left 设置为 root.right，因此您的 root.right 等于它自己。

Answer 2

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

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

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

无法理解为什么在尝试反转二叉树时必须创建新的临时 TreeNode

Trouble understanding why a new temporary TreeNode has to be created when trying to invert a binary tree

java

recursion

binary-tree