# preface

Preparation basis Xiuyan teacher's Brochure Combined with leetcode Binary tree of sword finger offer Learn this part.

# Non recursive implementation of first order, second order, middle order and sequence traversal

In my understanding, a tree is a special kind of graph. The first order corresponds to the depth traversal of the graph, while the sequence corresponds to the breadth traversal of the graph.

The recursive implementation of first order and second order is still relatively easy to understand. For non recursive implementation, manually implement a recursive stack.

When I first learned the data structure, I followed the mooc of Zhejiang University. There is a well understood explanation for the traversal of trees:

The order read out according to the cross is the pre order traversal, which happens to pass through the node for the first time

The order read out according to the asterisk is the middle order traversal, which happens to pass through the node for the second time

The order read out according to the triangle is post order traversal, which happens to pass through the node for the third time

ok draw not much on ~ on the code

## Preorder traversal

We need to pay attention to a stack order of the stack array.

As we all know, the (x) priority is the order of root = > left = > right ~ so when entering the stack, you should first right and then left to ensure that the left is always accessed first when bouncing the stack.

```/**
* @param {TreeNode} root
* @return {number[]}
*/
const preorderTraversal = function(root) {
// Define result array
const res = []
// Dealing with boundary conditions
if(!root) {
return res
}
// Initialize stack structure
const stack = []
// First, put the root node into the stack
stack.push(root)
// If the stack is not empty, repeat the operations of out stack and in stack
while(stack.length) {
// Record the top node of the stack as the current node
const cur = stack.pop()
// The current node is the root node of the current subtree. Put this node at the end of the result array
res.push(cur.val)
// If the root node of the current subtree has a right child, the right child will be put into the stack
if(cur.right) {
stack.push(cur.right)
}
// If the root node of the current subtree has a left child, the left child will be put into the stack
if(cur.left) {
stack.push(cur.left)
}
}
// Return result array
return res
};```

## Postorder traversal

Hey, in fact, post order traversal and pre order traversal are still very similar!

As we all know, the order after (x) is ， left = > right = > root

When traversing, we will always access the root first.

So there is a good way. Before, we added a val at the end of the res array. In the post order, you can add a val at the head of the res array instead. (equivalent to changing res from a queue to a stack)

Correspondingly, originally considering the stack, we always put right at the bottom of the stack and left at the top of the stack.

This idea will be reversed when traversing in the later order. We should press left first and then right~

This will also be popped out first and pushed into the res array. The order of ~ res will become: left = > right = > root

```/**
* @param {TreeNode} root
* @return {number[]}
*/
const postorderTraversal = function(root) {
// Define result array
const res = []
// Dealing with boundary conditions
if(!root) {
return res
}
// Initialize stack structure
const stack = []
// First, put the root node into the stack
stack.push(root)
// If the stack is not empty, repeat the operations of out stack and in stack
while(stack.length) {
// Record the top node of the stack as the current node
const cur = stack.pop()
// The current node is the root node of the current subtree. Put this node at the head of the result array
res.unshift(cur.val)
// If the root node of the current subtree has a left child, the left child will be put into the stack
if(cur.left) {
stack.push(cur.left)
}
// If the root node of the current subtree has a right child, the right child will be put into the stack
if(cur.right) {
stack.push(cur.right)
}
}
// Return result array
return res
};```

# Middle order traversal

Compared with the first two similar traversal methods, the middle order traversal is somewhat out of place (x)

As we all know, the order in (x) is the order of {left = > root = > right

Code idea:
While (stack non null 𞓜 pointer non null):
Stack the left subtree of all// Include root node
Outbound access;
The pointer points to the right node

This also has the advantage that when accessing out of the stack, the root point is actually accessed. Then, right will be put on the stack to ensure the traversal order~

```/**
* @param {TreeNode} root
* @return {number[]}
*/
const inorderTraversal = function(root) {
// Define result array
const res = []
// Initialize stack structure
const stack = []
// Using a cur node as a cursor
let cur = root
// When cur is not empty or stack is not empty, repeat the following logic
while(cur || stack.length) {
// The function of this while is to record all nodes of the path in the process of finding the leftmost leaf node
while(cur) {
// Stack the nodes of the path
stack.push(cur)
// Continue to search the left child of the current node
cur = cur.left
}
// Take out the top element of the stack
cur = stack.pop()
// Put the top element on the stack
res.push(cur.val)
// Try to read the right child of cur node
cur = cur.right
}
// Return result array
return res
};```

## level traversal

Xiuyan teacher quoted a question here about sequence traversal. I think sequence traversal is relatively simple. It's easy to understand by looking at the code directly~

Title Description: give you a binary tree. Please return the node values obtained by traversing in sequence. (that is, access all nodes from left to right layer by layer).

```/**
* @param {TreeNode} root
* @return {number[][]}
*/
const levelOrder = function(root) {
// Initialize result array
const res = []
// Dealing with boundary conditions
if(!root) {
return res
}
// Initialize queue
const queue = []
// The first element of the queue is the root node
queue.push(root)
// When the queue is not empty, repeat the following logic
while(queue.length) {
// level is used to store the nodes of the current layer
const level = []
// Cache the queue length when it first enters the loop. This step is critical because the queue length will change later
const len = queue.length
// Loop through the nodes of the current level
for(let i=0;i<len;i++) {
// Fetch the header element of the queue
const top = queue.shift()
// Push the value of the header element into the level array
level.push(top.val)
// If the current node has left children, it will be pushed to the next level
if(top.left) {
queue.push(top.left)
}
// If the current node has a right child, push it to the next level
if(top.right) {
queue.push(top.right)
}
}
// Push level into result array
res.push(level)
}
// Return result array
return res
};```

# Sword finger offer

Recently, I was brushing my sword finger offer with classmate Zhou according to the tag. The progress is one question a day. Recently, I found that the lc mobile phone version is easy to use. I can use my mobile phone to brush questions during the subway and lunch break~

## Sword finger Offer 27 Image of binary tree

The problem was finished without looking at the teacher's pamphlet.

The idea is also very simple: recursively, traverse each node in the tree, and exchange the left and right children of each node.

```/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
//Define recursive boundaries
if(root) {
//Swap left and right subtrees
let tmp = root.left
root.left = root.right
root.right = tmp
//recursion
mirrorTree(root.left)
mirrorTree(root.right)

return root
}else {
return root
}
};```

## Sword finger Offer 28 Symmetric binary tree

It is also a recursive problem.

Because it is to judge symmetry, from the root node, whether the left is equal to the right.

If equal to, judge:

1. Is the left node of the left node equal to the right node of the right node

2. Is the right node of the left node equal to the left node of the right node

```var isSymmetric = function(root) {
return check(root, root)
};

const check = (leftPtr, rightPtr) => {
// Returns true if there is only a root node
if (!leftPtr && !rightPtr) return true
// If there is only one left and right node, false is returned
if (!leftPtr || !rightPtr) return false

return leftPtr.val === rightPtr.val && check(leftPtr.left, rightPtr.right) && check(leftPtr.right, rightPtr.left)
}

```

## Sword finger Offer 37 Serialized binary tree

I've used this question

```//serialize
var serialize = function(root) {
let res=[]
let queue=[root]
while(queue.length){
let node=queue.shift()
if(node){
res.push(node.val)
queue.push(node.left)
queue.push(node.right)
}else{
res.push('X')
}
}
return res.join(',')
};

//Deserialization
var deserialize = function(data) {
if (data == 'X') return null;

// Serialize string split into array
const list = data.split(',');
// Get the first item and build the root node
const root = new TreeNode(list[0]);
// Root node push queue
const queue = [root];
// Initial point to the second item of the list
let cursor = 1;
// The pointer is out of bounds, that is, the serialized string is swept
while (cursor < list.length) {
// Examine the nodes of the column
const node = queue.shift();
// The value of its left son
const leftVal = list[cursor];
// The value of its right son
const rightVal = list[cursor + 1];

// Judge whether it is a real node
if (leftVal != 'X') {
const leftNode = new TreeNode(leftVal);
node.left = leftNode;
queue.push(leftNode);
}

if(rightVal != 'X'){
const rightNode = new TreeNode(rightVal);
node.right=rightNode;
queue.push(rightNode);
}
// Visit a pair of sons at a time and add 2 to the pointer
cursor += 2;
}
return root;
};
```

Added by ffsja on Tue, 08 Feb 2022 00:23:57 +0200