Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Recursion:
public class Solution { //Time: O(n) Space: O(depth of tree) public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } private void inorder(TreeNode root, ArrayList<Integer> res) { if (root == null) { return; } //res.add(root.val); pre inorder(root.left, res); //res.add(root.val); in inorder(root.right, res); //res.add(root.val); post } }
Iterative: Inorder
使用一个stack,如果有左子树,就把当前点放进stack,反之pop出一个node,检查它的右子树。
public class Solution { //Time: O(n) Space: O(depth of tree) public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; while (!stack.isEmpty() || p != null) { if (p != null) { stack.push(p); p = p.left; } else { p = stack.pop(); res.add(p.val); p = p.right; } } return res; } }
Iterative: Preorder
用一个stack,当前node被pop出后,先push右子树节点,再push左子树节点
public class Solution { //Time: O(n) Space: O(n) public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); if (cur.right != null) { //push right first stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } res.add(cur.val); } return res; } }
Iterative: Postorder
public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode pre = null; TreeNode cur = root; stack.push(root); while (!stack.isEmpty()) { cur = stack.peek(); if (pre == null || pre.left == cur || pre.right == cur) { if (cur.left != null) { stack.push(cur.left); } else if (cur.right != null) { stack.push(cur.right); } } else if (cur.left == pre) { if (cur.right != null) { stack.push(cur.right); } } else { res.add(cur.val); stack.pop(); } pre = cur; } return res; } }
No comments:
Post a Comment