# 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; };