理解

二叉树的遍历通常有三种模式：前序、中序、后序、层序遍历。比如，以下这棵树对应的遍历结果为：

• 前序：3、9、20、15、7
• 中序：9、3、15、20、7
• 后序：9、15、7、20、3
• 层序：3、9、20、15、7

递归遍历

递归写法理解起来比较简单，按照我们遍历的顺序执行递归函数即可。 我们先思考下 leetcode 几道题的递归做法：

144. 二叉树的前序遍历

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

94. 二叉树的中序遍历

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

145. 二叉树的后序遍历

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

102. 二叉树的层序遍历

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

迭代遍历

这里，前序、后序、层序遍历都可以灵巧地利用栈或者队列进行遍历，因为根是在叶子节点前/后遍历，不会出现交叉。 中序遍历则需要我们想清楚遍历过程中，我们是先向下查找，直到找到左子叶，将左子叶、根压入栈，之后右节点作为根继续遍历。

144. 二叉树的前序遍历

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

94. 二叉树的中序遍历

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

145. 二叉树的后序遍历

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

102. 二叉树的层序遍历

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

前期回顾

Leetcode303 区域和检索 | 刷题打卡

LeetCode 组合总和三连 | 刷题打卡

LeetCode 703 数据流中的第 K 大元素 | 刷题打卡

LeetCode 239 滑动窗口最大值 | 刷题打卡

LeetCode 242 有效的字母异位词 | 刷题打卡

LeetCode 15 三数之和 | 刷题打卡

LeetCode 98 验证二叉搜索树 | 刷题打卡

LeetCode 50. Pow(x, n) | 刷题打卡

LeetCode 103 & 199 & 542 | 刷题打卡

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情