# Binary Tree Traversal

## Depth traversal of binary trees

### Recursive traversal

1. Pre-order traversal
```class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
traverse(root.right);
}
}
```
1. Intermediate traversal
```class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
traverse(root.right);
}
}
```
1. Post-order traversal
```class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
traverse(root);
return res;
}
void traverse(TreeNode root) {
if(root == null) return;
traverse(root.left);
traverse(root.right);
}
}
```
1. 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);
}
```
1. 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

1. Pre-order traversal
```class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return new LinkedList<Integer>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode curNode = stack.pop();
if(curNode.right != null) {
stack.push(curNode.right);//Traversing Left Subtree
}
if(curNode.left != null) {
stack.push(curNode.left);//Traversing right subtree
}
}
return res;
}
}
```
1. Intermediate traversal
```class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new LinkedList<Integer>();
TreeNode curNode = root;
while(curNode != null || !stack.isEmpty()) {
while(curNode != null) {
stack.push(curNode);
curNode = curNode.left;//Traversing Left Subtree
}
curNode = stack.peek();
curNode = curNode.right;//Traversing right subtree
stack.pop();
}
return res;
}
}
```
1. 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
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 {
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;
}
}
```
1. 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;
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();
if(curNode.left != null) {
queue.offer(curNode.left);//Traversing Left Subtree
}
if(curNode.right != null) {
queue.offer(curNode.right);//Traversing right subtree
}
}