Description
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input:
[1,null,2,3]
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
Recursion, time O(n), space O(h)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postorderTraversalRecur(root, list);
return list;
}
public void postorderTraversalRecur(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorderTraversalRecur(root.left, list);
postorderTraversalRecur(root.right, list);
list.add(root.val);
}
}
Iteration with Stack, time O(n), space O(h)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
if (root == null) { // edge case
return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
Collections.reverse(list); // reverse in the end
return list;
}
}
Common solution, time O(n), space O(h)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
while (!stack.empty() || p != null) {
if (p != null) {
stack.push(p);
list.add(0, p.val); // add to the beginning before going to children
p = p.right; // go right
} else {
p = stack.pop().left; // go left
}
}
return list;
}
}