144. Binary Tree Preorder Traversal
Link: https://leetcode.com/problems/binary-tree-preorder-traversal/description/
Description
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Approach
Recursive
Traverse Order: root -> left -> right
Iterative
- Initialize a stack, and a list result.
- Push the root to the stack.
- While s is not empty:
- pop the top of the stack and add the value of the node to result.
- Push right to the stack if right is not null.
- Push left to the stack if left is not null.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this. val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this. left = left;
* this.right = right;
* }
* }
*/
//Recuisive
class Solution {<!-- -->
public List<Integer> preorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode root, List<Integer> result) {<!-- -->
if (root == null)
return;
result. add(root. val);
preorder(root. left, result);
preorder(root.right, result);
}
}
// Iterative
class Solution {<!-- -->
public List<Integer> preorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack. push(root);
while (!stack.isEmpty()) {<!-- -->
TreeNode temp = stack. pop();
result. add(temp. val);
if (temp. right != null)
stack.push(temp.right);
if (temp. left != null)
stack.push(temp.left);
}
return result;
}
}
// Iterative
class Solution {<!-- -->
public List<Integer> preorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack. push(root);
while (!stack.isEmpty()) {<!-- -->
TreeNode temp = stack. peek();
if (temp != null) {<!-- -->
stack. pop();
if (temp. right != null)
stack.push(temp.right);
if (temp. left != null)
stack.push(temp.left);
stack. push(temp);
stack. push(null);
}
else {<!-- -->
stack. pop();
temp = stack. pop();
result. add(temp. val);
}
}
return result;
}
}
94. Binary Tree Inorder Traversal
Link: https://leetcode.com/problems/binary-tree-inorder-traversal/description/
Description
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Approach
Recursive
Traverse Order: left -> root -> right
Iterative
Approach 1
The order of processing nodes and visiting nodes is different. So we need a stack to store the nodes and a pointer to indicate the visiting order.
- Initialize an empty stack and a pointer to the root node of the binary tree.
- While the stack is not empty or the current pointer is not null:
- If the current pointer is not null, push it onto the stack and move the pointer to its left child.
- If the current pointer is null, pop a node from the stack (which represents a parent node), process its value (store it in the result array), and move the pointer to its right child.
- Repeat the above two steps until all nodes are processed.’
Approach 2
Nodes that are visited are directly added to the stack, but if a node is being processed, an additional empty node is placed after it. This way, only when the empty node is popped, the next node is added to the result set.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this. val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this. left = left;
* this.right = right;
* }
* }
*/
class Solution {<!-- -->
public List<Integer> inorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode root, List<Integer> result) {<!-- -->
if (root == null)
return;
inorder(root. left, result);
result. add(root. val);
inorder(root.right, result);
}
}
//Iterative
class Solution {<!-- -->
public List<Integer> inorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {<!-- -->
if (cur != null) {<!-- -->
stack.push(cur);
cur = cur. left;
}
else {<!-- -->
cur = stack. pop();
result. add(cur. val);
cur = cur.right;
}
}
return result;
}
}
// Iterative approach 2
class Solution {<!-- -->
public List<Integer> inorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack. push(root);
while (!stack.isEmpty()) {<!-- -->
TreeNode temp = stack. peek();
if (temp != null) {<!-- -->
stack. pop();
if (temp. right != null)
stack.push(temp.right);
stack. push(temp);
stack. push(null);
if (temp. left != null)
stack.push(temp.left);
}
else {<!-- -->
stack. pop();
temp = stack. pop();
result. add(temp. val);
}
}
return result;
}
}
145. Binary Tree Postorder Traversal
Link: https://leetcode.com/problems/binary-tree-postorder-traversal/
Description
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Approach
Recursive
Traverse Order: left -> right -> root
Iterative
The order of preorder is root -> left -> right, we can make a small change to the code and change it to root -> right -> left. Then we can reverse the result list, and turn it to left -> right -> root, which is the result of postorder traversal.
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this. val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this. left = left;
* this.right = right;
* }
* }
*/
//Recursive
class Solution {<!-- -->
public List<Integer> postorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode root, List<Integer> result) {<!-- -->
if (root == null)
return;
postorder(root. left, result);
postorder(root.right, result);
result. add(root. val);
}
}
//Iterative
class Solution {<!-- -->
public List<Integer> postorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack. push(root);
while (!stack.isEmpty()) {<!-- -->
TreeNode temp = stack. pop();
result. add(temp. val);
if (temp. left != null)
stack. add(temp. left);
if (temp. right != null)
stack. add(temp. right);
}
Collections. reverse(result);
return result;
}
}
//Iterative
public List<Integer> postorderTraversal(TreeNode root) {<!-- -->
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
stack. push(root);
while (!stack.isEmpty()) {<!-- -->
TreeNode temp = stack. peek();
if (temp != null) {<!-- -->
stack. pop();
stack. push(temp);
stack. push(null);
if (temp. right != null)
stack.push(temp.right);
if (temp. left != null)
stack.push(temp.left);
}
else {<!-- -->
stack. pop();
temp = stack. pop();
result. add(temp. val);
}
}
return result;
}
}
Reference: https://programmercarl.com/