sammy333 - 6 months ago 45
Java Question

# What is wrong with my Preorder traversal?

I am trying to solve this problem https://oj.leetcode.com/problems/binary-tree-preorder-traversal/ , i.e. preorder traversal with recursive slution.

EDIT: The whole code:

``````import java.util.ArrayList;
import java.util.List;

public class Solution {

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
static List<Integer> res = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
if(root.left != null){
}
if(root.right != null){
}
return res;
}
}
``````

I have wrong answer because of the following:

``````Input:  {1,2}
Output:     [1,1,2]
Expected:   [1,2]
``````

Can someone tell me how to fix this?

EDIT: I dont have
`main()`
method or unit tests. If you open the link that I posted you will see that this is online judging system.

The problem is that within each recursive loop, you are adding the entire array again into your final result.

For example, given the following tree:

```  1
/
2```

Your first iteration adds 1 into 'res' variable. The problem is when it gets to this line:

``````res.add(preorderTraversal(root.left));
``````

Then it recursively calls itself for the left side. That preorderTraversal will return the res array, which will be [1,2]. Hence, when [1,2] gets added to res (which was [1], remember?), then you get [1,1,2].

Here's code that should work:

``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();

if(root == null){
return result;
}