Why I got wrong answer


  • 0
    S
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> treeNode = new ArrayList<Integer>();
        if(root == null)
            return treeNode;
        treeNode.add(root.val);
        if(root.left != null){
            preorderTraversal(root.left);
        }
        if(root.right != null){
            preorderTraversal(root.right);
        }
        return treeNode;
    }

  • 0
    M

    At each level of your algorithm, you create a new ArrayList called treeNode. While all of them have the same name at the source code level, they actually all point to different lists. What is happening is that at each level you create your tree, add the node at that level, and return the list, since nothing is done about the trees returned to you from the children of the node.

    Try replacing the children calls with treeNode.addAll(preorderTraversal(root.left)); and treeNode.addAll(preorderTraversal(root.right));.

    That way, the trees returned by the children will be added into the list you are building for the current node.

    On a side note, you can also solve this by passing a single list through the tree and adding to that instead of creating a list at each level, or using a single list as a global variable and erasing it before a run.

    Of course, these are all based on your recursive solution, and according to the problem, the goal is to solve it iteratively. Good luck with your future efforts.


  • 0
    S

    Thank you, I just put ArrayList declaration out of the function, and it works.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.