Help me to check if this solution is right !


  • 0
    S

    I've see wikipedia's solution of visit tag , and also see a pre-order-likable solution using 2 stack, and a normal one-stack solution. But when I tried to reduce it by myself, I got a brand new different answer:

    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        TreeNode current = root;
        if (current == null) {
            return array;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.empty() || current != null) {
            while (current != null) {
                stack.push(current);
                if (current.right != null) {
                    stack.push(current);
                }
                current = current.left;
            }
            current = stack.pop();
            if (!stack.empty() && current == stack.peek()) {
                current = current.right;
            } else {
                array.add(current.val);
                current = null;
            }
        }
        return array;
    }
    

    It's a simple case for

      a
     / \
    b   c
    

    It got a sequence like this:

    push a
    push a
    push b
    pop // b
    pop // a ; but we don't need to handle it
    push c
    pop // c
    pop // a
    

    I just thought that we can push parent twice to avoid using prev helper variable.
    It's accepted, but I dunno whether it's right.


  • 0
    W

    i think the sequence like this:
    push a
    pop a // pop a and find it needs to hanldle ,else we will push again
    push a
    push c
    push b
    pop b // b
    pop c // c
    pop a // a


Log in to reply
 

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