Inverse A Tree LeetCode

user_11178048 0
Viewed 105

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

Problem:

image of the 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?

binary-tree java
1 Answers

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.

user_24428040
Related