List a Tree's Values Left, Right, Node
Solve this ProblemYou are given the root of a binary tree. Return the values of all its nodes in the order you meet them when, at every node, you walk the entire left subtree first, then the entire right subtree, and only then take the node itself.
Recursion expresses this directly. Without recursion it can be done with one stack by producing the mirror order (node, right subtree, left subtree) and reversing the result.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Every node comes after both of its subtrees: first the whole left subtree, then the whole right subtree, then the node itself. Return the values in that order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Walk
GoodA helper walks the whole left subtree, then the whole right subtree, and only then records the node's own value — so a node is always recorded after everything below it. A missing child returns at once. Each node is entered once (O(n) time) and the recursion is as deep as the tree is tall, giving O(h) extra space (O(n) for a single long chain).
O(n)O(h)1class Solution {
2 public List<Integer> postorderValues(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 walk(root, out);
5 return out;
6 }
7
8 private void walk(TreeNode node, List<Integer> out) {
9 if (node == null) return;
10 walk(node.left, out);
11 walk(node.right, out);
12 out.add(node.val);
13 }
14}Optimal — One Stack, Then Reverse
OptimalDo the mirror image of the easy order: with one stack, take a node, record it, and push its left child and then its right child, so the right child is popped first. That produces node, right subtree, left subtree. Reversing that list gives left subtree, right subtree, node — exactly the order asked for. One pass with a stack plus one reverse: O(n) time. The stack is O(h), but the collected list is O(n) before reversing.
O(n)O(n)1class Solution {
2 public List<Integer> postorderValues(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 if (root == null) return out;
5 Deque<TreeNode> stack = new ArrayDeque<>();
6 stack.push(root);
7 while (!stack.isEmpty()) {
8 TreeNode node = stack.pop();
9 out.add(node.val);
10 if (node.left != null) stack.push(node.left);
11 if (node.right != null) stack.push(node.right);
12 }
13 Collections.reverse(out);
14 return out;
15 }
16}