逆A树LeetCode

Question

因此，我在LeetCode上做了一个问题，在这个问题上，我必须反转一个二叉树。

问题：

​

​

我的解决方案是：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        TreeNode newTree = root;
        return invertTreeHelper(root, newTree);
    }

    public TreeNode invertTreeHelper(TreeNode root, TreeNode newTree)
    {
       if(root == null)
           return null; 
        
       newTree.val = root.val;         
       newTree.left = invertTreeHelper(root.right, newTree.left); 
       newTree.right = invertTreeHelper(root.left, newTree.right); 
       return newTree; 
    }
}

给定的输入是：

[4,2,7,1,3,6,9]

我的预期产出是：

[4,7,2,9,6,3,1]

但是，我的输出是：

[4,7,7,9,6,6,9]

因此，很明显，我的输出不适用于树的左侧。我想知道我哪里出了问题。有人能帮我吗？

Answer 1

newTree = root意味着，如果您现在更改newTree.left，您也更改了root.left，您没有实际的新树，您只需在适当的位置操作一棵树。如果你想这样做，你必须小心，不要覆盖你以后需要的东西。如果您想交换两个数字，则不能写入a=b; b=a;，因为在第二次赋值时，a已经被更改。但是你只是用left和right来做这个。

基本上你应该写：

public void invertTree(TreeNode node) {
   if (node == null)
       return; 
    TreeNode tmp = node.left;
    node.left = node.right
    node.right = tmp;
    invertTree(node.left);
    invertTree(node.right);
}

或者，您实际上可以创建一个新树，然后您不需要担心tmp部分，但是您需要在正确的位置使用相当多的new TreeNode语句，那么您就不能在原始树和新树中都使用节点。