Binary tree algorithm is still very important in the front-end interview, almost is the last question algorithm questions will be asked, so it is necessary to understand the binary tree traversal calculation method, today we will discuss the binary tree traversal calculation method.

Binary tree sequential traversal algorithm formula

  • Accessing the root node
  • Preemptive traversal of the left subtree of the root node
  • Preemptive traversal of the right subtree of the root node

Preorder traversal recursive version

const bt = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null }, right: { val: 5, left: null, right: null } }, right: { val: 3, left: { val: 6, left: null, right: null }, right: { val: 7, left: null, right: null } } } const preorder = (root) => { if(! root) return console.log(root.val) preorder(root.left) preorder(root.right) } preorder(bt)Copy the code

Preemptive traversal of the non-recursive version

// Const preorder2 = (root) => {if(! root) return const stack = [root] while(stack.length) { const n = stack.pop() console.log(n) n.right && stack.push(n.right) n.left && stack.push(n.left) } }Copy the code

Middle order traversal calculation formula

  • Middle order traversal of the left subtree of the root node
  • Accessing the root node
  • Middle order traversal is performed on the right subtree of the root node

Order traversal recursive version

const inorder = (root) => { if(! root) return inorder(root.left) console.log(root.val) inorder(root.right) }Copy the code

Non-recursive version of order traversal

const inorder2 = (root) => { if(! Root) return const stack = [] let p = root First point to the root node while (stack length | | p) {while (p) {/ / the left subtree are pushed into the first stack stack. Push (p) p = p.l eft} const n = stack. Pop () Console. log(n.val) p = n.right}}Copy the code

After the sequential traversal calculation formula

  • A post-order traversal of the left subtree of the root node is performed
  • A post-order traversal is performed on the right subtree of the root node
  • Accessing the root node

Post – order traversal recursive version

const postorder = (root) => { if(! root) return postorder(root.left) postorder(root.right) console.log(root.val) }Copy the code

Post – order traversal non – recursive version

The order of the first traversal is root-left-right, and the order of the second traversal is left-right-root, and the order of the second traversal is root-right-left, and the order of the second traversal is left-right-root

const postorder2 = (root) => { if(! root) return const stack = [root] const outputStack = [] while(stack.length) { const n = stack.pop() outputStack.push(n)  n.left && stack.push(n.left) n.right && stack.push(n.right) } while(outputStack.length) { const n = outputStack.pop() console.log(n.val) } }Copy the code

conclusion

Recursive version of the traversal is easier to have ideas to achieve, that in fact, the non-recursive version of traversal is actually just changed to the stack, but it is the same, because in a function to call another function, itself will form a function call stack, each function is released after execution. So our final implementation is to use a stack to simulate recursion.