Title Link
leetcode-144: prefix traversal
leetcode-94: intermediate traversal
leetcode-145: post-order traversal
leetcode-102: Sequence traversal
Depth traversal of binary trees
Recursive traversal
- Pre-order traversal
class Solution {
List<Integer> res = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
res.add(root.val);
traverse(root.left);
traverse(root.right);
}
}
- Intermediate traversal
class Solution {
List<Integer> res = new LinkedList<>();
public List<Integer> inorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
res.add(root.val);
traverse(root.right);
}
}
- Post-order traversal
class Solution {
List<Integer> res = new LinkedList<>();
public List<Integer> postorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
traverse(root.right);
res.add(root.val);
}
}
- summary
(1) Iteration should not be entangled in details, but should pursue logical self-consistency.
(2) Template framework for binary trees:
void traverse(TreeNode root) {
if(root == null) return;//Conditions for Judging Return
//Preorder Code Location
traverse(root.left);
//Intermediate Code Location
traverse(root.right);
//Postorder Code Location
}
(3) Recursive functions I roughly think of as loops, similar to traversal of arrays, but this is a binary tree traversal. The following code is the framework of the loop, roughly assuming that as long as traverse (or other nouns) occurs three times at the same time, the loop is complete, and the corresponding array loop has i<nums. If length is a condition, then recursion should also have a termination condition, that is, if(root == null) return. There is also a loop body in the array, that is, what you want to do. In the corresponding recursive function, the prefix, middle, or postorder code position is your loop body.
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
}
- The three parts of recursion:
(1) Determining the return value of a function and defining the function
(2) Determine termination conditions to be recursive
(3) Determine single-level recursive logic, that is, assuming you are standing on a node, what you need to do, what you need to know, and write these codes to the prefix, middle, or postorder code locations to solve the problem.
Iterative traversal
- Pre-order traversal
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return new LinkedList<Integer>();
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> res = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode curNode = stack.pop();
res.add(curNode.val);//Preorder Code Location
if(curNode.right != null) {
stack.push(curNode.right);//Traversing Left Subtree
}
if(curNode.left != null) {
stack.push(curNode.left);//Traversing right subtree
}
}
return res;
}
}
- Intermediate traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new LinkedList<Integer>();
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curNode = root;
LinkedList<Integer> res = new LinkedList<>();
while(curNode != null || !stack.isEmpty()) {
while(curNode != null) {
stack.push(curNode);
curNode = curNode.left;//Traversing Left Subtree
}
curNode = stack.peek();
res.add(curNode.val);//Intermediate position code
curNode = curNode.right;//Traversing right subtree
stack.pop();
}
return res;
}
}
- Post-order traversal
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return new LinkedList<Integer>();
List<Integer> res = new LinkedList<>();//Exist Binary Tree Node
LinkedList<TreeNode> stack = new LinkedList<>();//Maintain a stack
TreeNode curNode = root;//Maintain a current node
TreeNode visitNode = root;//Maintain an accessed node
while(curNode != null || !stack.isEmpty()) { //Stack is not empty or current node is not a leaf node
while(curNode != null) {
stack.push(curNode);//Push
curNode = curNode.left;//Traversing Left Subtree
}
curNode = stack.peek();
if(curNode.right != null && curNode.right != visitNode) {
curNode = curNode.right;//Traversing right subtree
} else {
res.add(curNode.val);//Postorder Code Location
visitNode = curNode;//Set current node as visited node
curNode = null;//Set current node to empty to prevent re-access
stack.pop();//Stack Out
}
}
return res;
}
}
- summary
(1) All three of the above ways of iterating a binary tree require maintaining a stack, because recursion is what stacks are.
(2) Pre-order iteration requires stack, intermediate iteration requires stack, curNode, and pre-order iteration requires stack, curNode, visitNode.
(3) When writing code, note that stack <TreeNode> and if (root == null) return new LinkedList <Integer>() do not make mistakes.
(4) The preceding traversal code is the right subtree first, then the left subtree, and the middle and the last order are the left subtree then the right subtree.
Width Traversal of Binary Trees
level traversal
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()) {
int n = queue.size();//Current queue size
List<Integer> list = new ArrayList<>();
for(int i=0; i<n; i++) {
TreeNode curNode = queue.poll();
list.add(curNode.val);
if(curNode.left != null) {
queue.offer(curNode.left);//Traversing Left Subtree
}
if(curNode.right != null) {
queue.offer(curNode.right);//Traversing right subtree
}
}
result.add(list);
}
return result;
}
}
- summary
(1) Sequence traversal is very similar to preceding traversal, which uses a one-way queue to traverse the left subtree before the right subtree. The latter uses a stack to traverse the right subtree first, then the left subtree.
(2) Sequence traversal within a loop may or may not be maintained, depending on the circumstances.
Rings are invincible, big and cute 😄