The former sequence traversal

LeetCode topic

recursive

var preorderTraversal = function(root) {
  const res = [];
  // Recursive function
  function _preorder(node) {
    if(! node)return;
    res.push(node.val);
    _preorder(node.left);
    _preorder(node.right);
  }
  _preorder(root);
  return res;
};
Copy the code

The iteration

Through the stack data structure (in and out), we can push the parent node into the stack, and perform the operation of the stack, each time the right child of the node out of the stack is pushed into the stack first, followed by the left child. In this way, we can first traverse the parent node, then traverse the left child part, and then traverse the right child part.

var preorderTraversal = function(root) {
  if(! root)return [];
  const stack = [root];
  const res = [];
  while(stack.length) {
    / / out of the stack
    const cur = stack.pop();
    res.push(cur.val);
    // The child nodes are pushed on the stack, first right and then left
    cur.right && stack.push(cur.right);
    cur.left && stack.push(cur.left);
  }
  return res;   
};
Copy the code

In the sequence traversal

LeetCode topic

recursive

var inorderTraversal = function(root) {
  const res = [];
  // Recursive function
  function _inorder(node) {
    if(! node)return;
    _inorder(node.left);
    res.push(node.val);
    _inorder(node.right);
  }
  _inorder(root);
  return res;
};
Copy the code

The iteration

We can also use the stack structure to implement in-order traversal, because in in-order traversal, the left subtree is traversed first, so the parent node is pushed on the stack before the nodes in the subtree, and every time we push a node, we push all the left nodes of the node’s left subtree on the stack.

var inorderTraversal = function(root) {
  if(! root)return [];
  const stack = [];
  let cur = root;
  const res = [];
  while (stack.length || cur) {
    // Push the left node first
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    const node = stack.pop();
    res.push(node.val);
    if(node.right ! =null) { cur = node.right; }}return res;
};
Copy the code

After the sequence traversal

LeetCode topic

recursive

var postorderTraversal = function(root) {
  const res = [];
  // Recursive function
  function _postorder(node) {
    if(! node)return;
    _postorder(node.left);
    _postorder(node.right);
    res.push(node.val);
  }
  _postorder(root);
  return res;
};
Copy the code

The iteration

Postorder traversal is when the parent node needs to be traversed last. But you can do it much the same way as you would do with pre-order traversal, except that when we insert an array, we always insert in the head, so that the value of the node that is inserted first is relative to the value of the left and right children.

var postorderTraversal = function(root) {
  if(! root)return null;
  const res = [];
  const stack = [root];
  while (stack.length) {
    const cur = stack.pop();
    // Always insert the head, the first to be inserted after.
    res.unshift(cur.val);
    cur.left && stack.push(cur.left);
    cur.right && stack.push(cur.right);
  }

  return res;
};
Copy the code

Sequence traversal

LeetCode topic

recursive

var levelOrder = function(root) {
  const res = [];
  function _levelOrder(node, level) {
    if(! node)return null;
    // Initialize the current layer array
    res[level] =  res[level] || [];
    res[level].push(node.val);
    // The next layer is +1
    _levelOrder(node.left, level + 1);
    _levelOrder(node.right, level + 1);
  }
  _levelOrder(root, 0);

  return res;
};
Copy the code

The iteration

We use queues to hold nodes, and in each round of the loop, we take a layer out, and we put their left and right children in the queue.

var levelOrder = function(root) {
  if (root == null) return [];
  const ans = [];
  let level = 0;
  const queue = [root];
  while(queue.length) {
    ans.push([]);
    const len = queue.length;
    // By iterating through all the elements in a layer, the level can be +1
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      ans[level].push(node.val);
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
    level++;
  }
  return ans;
};
Copy the code

conclusion

About the foreword, middle order and subsequent traversal of binary tree, recursive method need not say more, mainly is the iterative method, through the application of the stack, the different order of nodes pressed into the stack, so as to realize the traversal of different order. Binary tree sequence traversal iteration is through the application of queue.