疊代法實作對二叉樹的前中後序周遊

題目描述

對二叉樹的周遊是面試中常出現的題目，二叉樹的前中後序周遊可以通過遞歸實作，也可以通過疊代實作，遞歸的方式在實際使用時，可能會面臨記憶體溢出的風險，是以掌握疊代法的周遊方式，對我們也是很關鍵的，讓我們來一起學會如何通過疊代法來周遊二叉樹吧！

前序周遊

首先，将根節點入棧，然後出棧的時候記錄其值，同時判斷其是否存在右子樹和左子樹，其中先判斷右子樹，再判斷左子樹，存在的話則将其壓入棧中，然後循環周遊棧，直到棧為空。

var preorderTraversal = function (root) {
  if (!root) return [];
  // 定義最終傳回的結果
  let result = [];
  // 定義棧
  const stack = [root];
  // 隻要棧中有元素則進入循環
  while (stack.length) {
    let node = stack.pop();
    result.push(node.val);
    // 如果右孩子存在的話
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return result;
};
複制代碼      

中序周遊

中序周遊的疊代法核心思想在于先周遊完左子樹，然後周遊根節點，然後周遊右子樹，先使用while循環，遇到左子節點，就讓左子節點入棧，如果出棧元素有右子樹，就讓目前節點指向這顆右子樹。

var inorderTraversal = function(root) {
  // 如果節點為空的情況
  if (!root) return [];
  // 定義最終傳回的結果
  const result = [];
  // 目前處理節點
  let cur = root;
  // 定義輔助棧
  let stack = [];
  // 核心循環
  while (stack.length || cur) {
    // 首先周遊左子樹
    while (cur) {
      stack.push(cur);
      cur = cur.left;
    }
    // 出棧，存儲
    let node = stack.pop();
    result.push(node.val);
    if (node.right) {
      cur = node.right
    }
  }
  return result;
};
複制代碼      

後序周遊

後序周遊的疊代法核心思路在于，将目前節點的值優先插入棧首，然後左孩子存在将左孩子入棧，右孩子存在将右孩子入棧。

var postorderTraversal = function(root) {
  if (!root) return []
  // 定義最終傳回的結果
  let result = [];
  // 定義輔助棧
  let stack = [root];
  // 隻要棧不為空就循環
  while (stack.length) {
    let node = stack.pop();
    result.unshift(node.val);
    // 記住，此處是先左後右
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }
  return result
};
複制代碼      

總結

二叉樹前中後序周遊的疊代法是非常重要的思路，主要是借助輔助棧來幫助我們周遊，無論是在工作中還是在面試中，這些思路都會幫助我們寫出更加精緻的代碼。