Algorithm Preorder(tree) 1. Visit the root. 2. Traverse the left subtree, i.e., call Preorder(left-subtree) 3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public List<Integer> preorderTraversal(TreeNode root){ List<Integer> ans = new ArrayList<>(); preOrder(root, ans); return ans; }
public List<Integer> preorderTraversal(TreeNode root){ List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) { return ans; } while (root != null || !stack.empty()) { while (root != null) { stack.push(root); ans.add(root.val); root = root.left; } root = stack.pop(); root = root.right; } return ans; }
Analysis
Time Complexity: O(n)
Space Complexity: O(n)
InOrder
1 2 3 4
Algorithm Inorder(tree) 1. Traverse the left subtree, i.e., call Inorder(left-subtree) 2. Visit the root. 3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
public List<Integer> inorderTraversal_rec(TreeNode root){ List<Integer> ans = new ArrayList<>(); inOrder(root, ans); return ans; }
publicvoidinOrder(TreeNode root, List<Integer> list){ if (root == null) { return; } if (root.left != null) { inOrder(root.left, list); } list.add(root.val); if (root.right != null) { inOrder(root.right, list); } }
public List<Integer> inorderTraversal(TreeNode root){ List<Integer> ans = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) { return ans; } while (root != null || !stack.empty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); ans.add(root.val); root = root.right; } return ans; }
Analysis
Time Complexity: O(n)
Space Complexity: O(n)
PostOrder
1 2 3 4
Algorithm Postorder(tree) 1. Traverse the left subtree, i.e., call Postorder(left-subtree) 2. Traverse the right subtree, i.e., call Postorder(right-subtree) 3. Visit the root.
Recursive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
public List<Integer> postorderTraversal_rec(TreeNode root){ List<Integer> ans = new ArrayList<>(); postOrder(root, ans); return ans; }