Help! Couldn't get the right answer!


  • 0
    H
    public class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> finalList = new ArrayList<Integer>();
        Stack<TreeNode> rst = new Stack<TreeNode>();
        TreeNode lastvisit = null;
       
        
        while(!rst.empty() || root!=null){
            if(root != null){
                rst.push(root);
                root = root.left;
            }else{
                TreeNode top = rst.peek();
                if(top.right!=null && lastvisit!=top.right){
                    rst.push(top.right);
                    root = top.right;
                }else{
                    finalList.add(top.val);
                    lastvisit = top;
                    rst.pop();
                }
            }
        }
        
        return finalList;
        
    }
    

    Got the wrong answer as below:

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

    I also tried the code with same input in Eclipse and print out some info as below:

    push TreeNode@70f87478 stack size1
    push TreeNode@47a6ac39 stack size3
    pop TreeNode@47a6ac39 stack size2
    pop TreeNode@47a6ac39 stack size1
    pop TreeNode@70f87478 stack size0
    [2, 2, 1]
    

    I think there is something while push/pop in /out from the stack.

    I appreciate any help on my code!


  • 0
    C

    if(top.right!=null && lastvisit!=top.right){
    rst.push(top.right);
    root = top.right;

    you should delete rst.push(top.right) here, because in the next recurtion, the code below:

    if(root != null)
    {rst.push(root);
    root = root.left;

    push root(top.right) into stack

    therefore, you have pushed top.right twice!


Log in to reply
 

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