Different results in LC and eclipse


  • 1
    A
    public class BinaryTreePreorderTraversal {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        if (root == null)
        	return ret;
        
        TreeNode node = root;
        ret.add(node.val);
        s.push(node);
        while (!s.isEmpty())
        {
        	if (node.left != null)
        	{
        		node = node.left;
        		ret.add(node.val);
        		s.push(node);
        	}
        	else
        	{
            	node = s.pop();
            	if (node.right != null)
            	{
            		node = node.right;
            		ret.add(node.val);
            		s.push(node);
            	}
        	}
        }
        
        return ret;
    }
    

    }

    Submission Result: Wrong Answer

    Input: {2,3,#,1}
    Output: [2,3,1,1]
    Expected: [2,3,1]

    I got return [2,3,1] in eclipse


  • 1
    G

    If I worked the test case on pen and paper, I get [2,3,1,1]. I am not sure, why eclipse gave [2,3,1] as the output.

    You algorithm is incorrect and it is very subtle, particularly node = s.pop();. Just work out this test case in paper, you can easily catch the bug -- draw the stack, ret, node.


Log in to reply
 

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