Question
Given a binary tree, return the postorder traversal of its nodes’ values.
Example:
Input:
[1,null,2,3]
1 \ 2 / 3
Output:
[3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution1 – Non-Recursive
/** * 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<Integer>(); if(root == null) return list; Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.push(root); while(!s1.isEmpty()){ TreeNode node = s1.pop(); s2.push(node); if(node.left!=null){ s1.push(node.left); } if(node.right!=null){ s1.push(node.right); } } while(!s2.isEmpty()){ TreeNode node = s2.pop(); list.add(node.val); } return list; } }
Solution2 – Recursive