Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3}
,1 \ 2 / 3return
[1,2,3]
.Note: Recursive solution is trivial, could you do it iteratively?
Time complexity: O(n)
Space complexity: O(n)
Code is below:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List preorderTraversal(TreeNode root) { // O(n) O(n) // recursive // LinkedList result = new LinkedList<>(); // traverse(root, result); // return result; // non-recursive LinkedList result = new LinkedList<>(); Stack stack = new Stack<>(); if (root == null) { return result; } stack.push(root); while(!stack.empty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; } public void traverse(TreeNode root, LinkedList result) { if (root == null) { return; } result.add(root.val); traverse(root.left, result); traverse(root.right, result); } }
Inorder:
Given a binary tree, return the inorder traversal of its nodes’ values.
Code is below:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List inorderTraversal(TreeNode root) { // O(n) O(n) // LinkedList result = new LinkedList<>(); // traverse(root, result); // return result; LinkedList result = new LinkedList<>(); Stack stack = new Stack(); if (root == null) { return result; } TreeNode cur = root; while (!stack.empty() || cur != null) { while (cur != null) { stack.add(cur); cur = cur.left; } cur = stack.peek(); stack.pop(); result.add(cur.val); cur = cur.right; } return result; } public void traverse(TreeNode root, LinkedList result) { if (root == null) { return; } traverse(root.left, result); result.add(root.val); traverse(root.right, result); } }
Postorder:
Given a binary tree, return the postorder traversal of its nodes’ values.
Code is below:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List postorderTraversal(TreeNode root) { // O(n) O(n) LinkedList result = new LinkedList<>(); traverse(root, result); return result; } public void traverse(TreeNode root, LinkedList result) { if (root == null) { return; } traverse(root.left, result); traverse(root.right, result); result.add(root.val); } }