A tree is a data structure that is often used to simulate a collection of data with a tree-like structure.

Binary tree is a more typical tree structure. As its name suggests, a binary tree is a tree structure in which each node has at most two subtrees, usually referred to as “left subtrees” and “right subtrees”.

The so-called vertical-traversal binary tree usually refers to pre-traversal, mid-traversal and post-traversal.

Recursive and iterative writing of the three traversals will be described below.

The iterative approach is to use a stack to store the left and right child nodes of each iteration.

The hypothesis tree is defined as follows:

 // Definition for a binary tree node.
 function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
 }
Copy the code

The former sequence traversal

The order of the preceding traversal is root node -> left child node -> right child node

Note: the stack is first in and then out, but pre-order traversal traverses the left child first and then the right child, so the right child needs to be pushed first

Then the recursive and iterative writing methods of the preceding traversal are as follows:

Var preorderTraversal = functioan (root) {let arr = [] const preNode = (point) => {if (point) { arr.push(point.val) preNode(point.left) preNode(point.right) } } preNode(root) return arr }; Var preorderTraversal = function(root) {let arr = [] let stack = [] if (root) stack.push(root (stack.length) { let point = stack.pop() arr.push(point.val) if (point.right) stack.push(point.right) if (point.left) stack.push(point.left) } return arr };Copy the code

In the sequence traversal

The order of middle traversal is left child -> root -> right child

So the recursive and iterative writing methods of middle order traversal are as follows:

Var inorderTraversal = function(root) {let arr = [] const midRoot = (point) => {if (point) {midRoot(point.left)  arr.push(point.val) midRoot(point.right) } } midRoot(root) return arr }; / var/iteration inorderTraversal = function (root) {let arr = [to] let the stack = [] while (root | | stack. The length) {while (root) { stack.push(root) root = root.left } root = stack.pop() arr.push(root.val) root = root.right } return arr };Copy the code

After the sequence traversal

The order of the back-order traversal is left child -> right child -> root node

Here after parsing the sequence traversal of the iterative method, also is to use a stack to save traversal of left and right child nodes, and sequence and the sequence traversal is not the same, I’m here to save the child nodes to save one more state to record, determine whether traverse the left and right child nodes The default is false, not traverse, when after we traverse the set to true

Then the recursive and iterative writing methods of post-order traversal are as follows:

// // var postorderTraversal = function(root) {let arr = [] const nextR = (point) => {if (point) { nextR(point.left) nextR(point.right) arr.push(point.val) } } nextR(root) return arr }; Var postorderTraversal = function(root) {let arr = [] let stack = [] if (root) stack. false]) while(stack.length) { let point = stack.pop() if (point[1]) { arr.push(point[0].val) } else { if (! point[0].left && ! point[0].right) { arr.push(point[0].val) } else { stack.push([point[0], true]) } if (point[0].right) stack.push([point[0].right, false]) if (point[0].left) stack.push([point[0].left, false]) } } return arr };Copy the code

conclusion

So that’s a couple of ways to write binary tree traversal. The following will continue to give several common scenarios and writing methods of binary tree traversal.