Short Java solution: stack + tracking explored nodes


  • 0
    P

    The key to this solution is keeping track of explored nodes. When a node has been fully explored (ie. its left and right children have been visited), it can be popped from the stack and added to the solution.

    public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> solution = new ArrayList<Integer>();
            if (root == null) {
                return solution;
            }
            Stack<TreeNode> stack = new Stack<TreeNode>();
            Set<TreeNode> explored = new HashSet<TreeNode>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode top = stack.peek();
                if (top.left != null && !explored.contains(top.left)) {
                    stack.push(top.left);
                } else if (top.right != null && !explored.contains(top.right)) {
                    stack.push(top.right);
                } else {
                    top = stack.pop();
                    explored.add(top);
                    solution.add(top.val);
                }
            }
            return solution;
        }
    

Log in to reply
 

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