英文:
Inverse A Tree 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:
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
已经被改变了。但你对 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
语句,然后你不能在原树和新树中都使用一个节点。
英文:
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>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论