[leetcode] 树的前序、中序的iterative traversal
Posted August 4, 2013
on:经典中的经典。
前序 pre order (中左右):
- push root
- pop,若有right, push right,若有left push left
- 这样继续一边pop一边push。直到stack为空。
public void preOrder(TreeNode root) { if (root == null) return; Stack<TreeNode> s = new Stack<TreeNode>(); s.push(root); while (!s.isEmpty()) { TreeNode top = s.pop(); System.out.print(top.val + ", "); if (top.right != null) s.push(top.right); if (top.left != null) s.push(top.left); } }
中序 in order (左中右):
- push root左支到死
- pop, 若pop的有right,则把right当root对待push它的左支到死。
- 这样继续一边pop一边push。直到stack为空。
public void inOrder(TreeNode root) { if (root == null) return; Stack<TreeNode> s = new Stack<TreeNode>(); pushAllTheyWayAtLeft(s, root); while (!s.isEmpty()) { TreeNode top = s.pop(); System.out.print(top.val + ", "); if (top.right != null) pushAllTheyWayAtLeft(s, top.right); } } private void pushAllTheyWayAtLeft(Stack<TreeNode> s, TreeNode root) { while (root != null) { s.push(root); root = root.left; } }
another way: keep a curr pointer, when curr is null means reached the left most, then start popping
public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode curr = root; while (!stack.isEmpty() || curr != null) { if (curr != null) { stack.push(curr); curr = curr.left; } else { curr = stack.pop(); result.add(curr.val); curr = curr.right; } } return result; }
Tags: converToIteration, tree
1 | Leetcode: reading time « juliachenonsoftware
June 10, 2015 at 1:16 pm
[…] https://leetcodenotes.wordpress.com/2013/08/04/classic-%E6%A0%91%E7%9A%84%E5%89%8D%E5%BA%8F%E3%80%81… […]