Iterative Postorder Traversal in Java, getting a TLE?


  • 0
    X

    hi, I used JAVA to implement this but got a TLE,
    any idea why this is happening? my code is attached below, thanks in advance!

    public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return new ArrayList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.peek();
            if(cur.left == null){
                if(cur.right == null){
                    result.add(cur.val);
                    cur = null;
                    stack.pop();
                }else{
                    stack.push(cur.right);
                }
            }else{ // cur.left != null
                stack.push(cur.left);
            }
        }
        return result;
    }
    

    }


  • 0
    S

    Could you please format your code correctly? Select all code and click {} button.


  • 1
    L

    I have not really tried to understand your code, but I can tell you easily why you're TLE-ing.

    You have a loop while the stack is not empty. You're pushing on the stack every node you encounter, but you're popping only the leaves. Your stack will never be empty.

    Also, two other remarks: 1) The line cur = null; seems totally useless. 2) You should not use the class Stack, use ArrayDeque with the interface Deque instead. (Deque<TreeNode> stack = new ArrayDeque<TreeNode>();)

    Have you tried first the recursive algorithm? It is much easier.


  • 0
    X

    thanks for your answer!

    1. The line cur = null; is used to set the current node to be null, so that its parent node will become leaf node when 2 children nodes are visited. Is this a wrong way to solve the problem or is there any implementation details I missed to cause the program fail?

    2. is there disadvantages using Stack?


  • 0
    T

    There is an infinity loop in your code. A node will only be popped if and only if both its left and right child is null, which is not true for all internal node. So the loop never exits.

    Just try the simplest case:
    1
    /
    2 3

    The output is like: 2, 3, 2, 3, 2, 3... Whenever the code returns to node "1", it keeps pushing "2" and "3" back to the stack.


  • 0
    F

    I have some ideas about your question. there are two possibilities when cur.left is not NULL, one is cur.right is NULL, the other is cur.right is not NULL. so i think you should write the loop of 'while' like this:

    while(!stack.isEmpty()){
        TreeNode cur = stack.peek();
        if(cur.left == null){
            if(cur.right == null){
                result.add(cur.val);
                cur = null;
                stack.pop();
            }else{
                stack.push(cur.right);
            }
        }else{ 
               if(cur.right == NULL)
                     stack.push(cur.left);
               else
               {
                     stack.push(cur.right); //push cur.right first, then push cur.left.
                     stack.push(cur.left);
               }
        }
    }

Log in to reply
 

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