Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}
, 1
\
2
/
3
return
[3,2,1]
.
Note: Recursive solution is trivial, could you do it iteratively?
Solution:
Recursive:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> solution = new ArrayList<Integer>(); postorderTraversal(root, solution); return solution; } public void postorderTraversal(TreeNode root, ArrayList<Integer> array) { if (root == null) return; postorderTraversal(root.left, array); postorderTraversal(root.right, array); array.add(root.val); } }
Iterative:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { HashSet<TreeNode> used = new HashSet<TreeNode>(); ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>(); ArrayList<Integer> solution = new ArrayList<Integer>(); if (root!=null) { stack.addFirst(root); } while(!stack.isEmpty()) { TreeNode temp = stack.removeFirst(); if(used.contains(temp)) solution.add(temp.val); else { used.add(temp); stack.addFirst(temp); if(temp.right != null) stack.addFirst(temp.right); if(temp.left != null) stack.addFirst(temp.left); } } return solution; } }
No comments :
Post a Comment