反转树 LeetCode

huangapple go评论90阅读模式
英文:

Inverse A Tree LeetCode

问题

我正在解决LeetCode上的一个问题,需要翻转一个二叉树。

问题:

反转树 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]

显然,我的输出在树的左侧部分无法正常工作。我想知道我哪里出错了。请问有人能帮助我吗?

英文:

So I am working on a problem on LeetCode where I must invert a binary tree.

Problem:

反转树 LeetCode

and here's my solution:

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; 
    }
}

The given input is:

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

My expected output is:

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

However, my output is:

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

So clearly, my output does not work for the left side of the tree. I want to know where I went wrong. Is anyone please able to help me with this?

答案1

得分: 3

newTree = root 的意思是,如果你现在改变了 newTree.left,你也会改变 root.left,你没有一个真正的新树,你只是在原地操作一棵树。如果你想要这样做,你必须小心,不要覆盖后面需要的东西。如果你想交换两个数字,你不能写 a=b; b=a;,因为在第二次赋值时 a 已经被改变了。但你对 leftright 就是这么做的。

基本上,你应该写:

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 语句,然后你不能在原树和新树中都使用一个节点。

英文:

newTree = root means that if you now change newTree.left you change root.left as well, you do not have an actual new tree, you just manipulate one tree in place. If you want to do that you must be careful not to overwrite stuff that you need later on. If you want to swap two numbers you cannot write a=b; b=a; since at the second assignment a would have already been changed. But you do just that with left and right.
Basically you should write:

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);
}

Alternatively you can actually create a new tree and then you do not need to worry about the tmp part but you would need quite a few new TreeNode statements at the right places, then you must not use a node in both the original and the new tree.

答案2

得分: -1

这是我从LeetCode的解决方案。这是一个带有后序遍历的简单递归问题。解决方案的时间复杂度为O(n),在LeetCode上的运行时间排名前1%,内存排名前3%。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 // 递归问题,在后序遍历中交换每个节点的左右子节点
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        if(root.left == null && root.right == null) {
            return root;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}
英文:

Heres my solution from leetcode. Its a simple recursion problem with a postorder traversal. Soln is 0(n) and it ranks top 1% in runtime and top 3% in memory on leetcode

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //recursion problem, swap every left with the right node in postorder 
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        if(root.left == null && root.right == null) {
            return root;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

</details>



huangapple
  • 本文由 发表于 2020年9月24日 16:11:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/64042143.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定