Description
Given a binary tree, return the postorder traversal of its nodes’ values.
Example
1 2 3 4 5 6 7 8
| Input: [1,null,2,3] 1 \ 2 / 3
Output: [3,2,1]
|
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
class Solution { List<Integer> res = new ArrayList<>(); public void postOrder(TreeNode node){ if (node.left != null) postOrder(node.left); if (node.right != null) postOrder(node.right); res.add(node.val); } public List<Integer> postorderTraversal(TreeNode root) { if (root == null) return res; LinkedList<Integer> result = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.addFirst(p.val); p = p.right; } else { TreeNode node = stack.pop(); p = node.left; } } return result; } }
|