sammy333 sammy333 - 29 days ago 11
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>();
}
res.add(root.val);
if(root.left != null){
res.add(preorderTraversal(root.left));
}
if(root.right != null){
res.add(preorderTraversal(root.right));
}
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.

Answer Source

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

    result.add(root.val);
    if(root.left != null){
        result.addAll(preorderTraversal(root.left));
    }
    if(root.right != null){
        result.addAll(preorderTraversal(root.right));
    }

    return result;
}