understand

There are three modes of binary tree traversal: pre-order, mid-order, back-order and hierarchical traversal. For example, the corresponding traversal result of the following tree is:

• Foreword: 3, 9, 20, 15, 7
• Middle order: 9, 3, 15, 20, 7
• Postsequence: 9, 15, 7, 20, 3
• Sequence: 3, 9, 20, 15, 7

The recursive traversal

The recursion is easier to understand, just execute the recursive functions in the order we iterate. Let’s think about recursion in Leetcode for a few problems:

144. Antecedent traversal of binary trees

var preorderTraversal = function (root) {
  let results = [];
  traversal(root);
  return results;
  function traversal(root) {
    if(! root) {return; } results.push(root.val); traversal(root.left); traversal(root.right); }};Copy the code

Middle order traversal of binary trees

var inorderTraversal = function (root) {
  let results = [];
  traversal(root);
  return results;
  function traversal(root) {
    if(! root) {return; } traversal(root.left); results.push(root.val); traversal(root.right); }};Copy the code

145. Back-order traversal of binary trees

var postorderTraversal = function (root) {
  let results = [];
  traversal(root);
  return results;
  function traversal(root) {
    if(! root) {return; } traversal(root.left); traversal(root.right); results.push(root.val); }};Copy the code

102. Sequence traversal of binary trees

var levelOrder = function (root) {
  if(! root)return [];
  let result = [];
  traversal(root, 0);
  return result;
  function traversal(node, level) {
    if(! node)return;
    if (result.length < level + 1) {
      result.push([]);
    }
    result[level].push(node.val);
    traversal(node.left, level + 1);
    traversal(node.right, level + 1); }};Copy the code

Iteration traversal

Here, front, back, and layer traversals can all be deftly traversed using stacks or queues, because the root traverses in front of/behind the leaf node, with no crossover. Middle-order traversal requires us to think clearly about whether we first look down until we find the left cotyledon, push the left cotyledon and the root, and then continue traversal as the root.

144. Antecedent traversal of binary trees

var preorderTraversal = function (root) {
  if(! root) {return [];
  }
  let results = [];
  let stack = [root];
  while (stack.length) {
    let node = stack.pop();
    results.push(node.val);
    if (node.right) {
      stack.push(node.right);
    }
    if(node.left) { stack.push(node.left); }}return results;
};
Copy the code

Middle order traversal of binary trees

var inorderTraversal = function (root) {
  if(! root) {return [];
  }
  let stack = [];
  let results = [];
  while (stack.length || root) {
    if (root) {
      stack.push(root);
      root = root.left;
    } else{ root = stack.pop(); results.push(root.val); root = root.right; }}return results;
};
Copy the code

145. Back-order traversal of binary trees

var postorderTraversal = function (root) {
  if(! root) {return [];
  }
  let results = [];
  let stack = [root];
  while (stack.length) {
    let node = stack.pop();
    results.unshift(node.val);
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }

  return results;
};
Copy the code

102. Sequence traversal of binary trees

var levelOrder = function (root) {
  if(! root) {return [];
  }
  let queue = [root],
    result = [];
  while (queue.length) {
    let level = [];
    let rest = [];
    while (queue.length) {
      let peek = queue.shift();
      if (peek) {
        level.push(peek.val);
        if (peek.left) {
          rest.push(peek.left);
        }
        if(peek.right) { rest.push(peek.right); } } } queue.push(... rest); result.push(level); }return result;
};
Copy the code

Preliminary review

Leetcode303 area and retrieve | punch brush

LeetCode portfolio combined three clock even | brush

LeetCode data flow of the first 703 K elements | punch brush

LeetCode 239 clock in a maximum sliding window | brush

LeetCode 242 effective letter clock in ectopic word | brush

Clock in 15 three sum LeetCode | brush

LeetCode 98 validation binary search trees | punch brush

LeetCode 50. The Pow (x, n) | punch brush

LeetCode 103 & 199 & 542 | punch brush

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign