JAVA solution using stack


  • 0
    R

    Use a class pair to store each node with boolean visited value, if the node have not been visited, then we search its children. If the node has been visited, add the value to list and pop().

    public class Solution {
        public class Pair{
            TreeNode node;
            boolean visited;
            public Pair(TreeNode node, boolean visited) {
                this.node = node;
                this.visited = visited;
            }
        }
        public List<Integer> postorderTraversal(TreeNode root) {
            if(root == null) {
                return new ArrayList<Integer>();
            }
            List<Integer> list = new ArrayList<Integer>();
            Stack<Pair> s = new Stack<>();
            s.push(new Pair(root, false));
            while(!s.isEmpty()) {
                Pair curr = s.peek();
                if(!curr.visited) {
                    if(curr.node.right!=null) {
                        s.push(new Pair(curr.node.right, false));
                    } 
                    if(curr.node.left!=null) {
                        s.push(new Pair(curr.node.left, false));
                    }
                    curr.visited = true;
                } else {
                    list.add(curr.node.val);
                    s.pop();
                }
            }
            return list;
        }
    }

Log in to reply
 

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