分析

遍历分类

前提：基础数据定义

// 二叉树定义
class Tree {
  val: number;
  left: Tree | null;
  right: Tree | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
// 二叉树实例
let treeRoot = (function () {
  let nodes = new Array(7).fill(0).map((value, index) => new Tree(index));
  nodes[0].left = nodes[1];
  nodes[0].right = nodes[2];
  nodes[1].left = nodes[3];
  nodes[1].right = nodes[4];
  nodes[2].left = nodes[5];
  nodes[2].right = nodes[6];
  let head = nodes[0];
  nodes.length = 0;
  return head;
})();

前中后递归

// 前序递归
let r1 = [];
function preOrderRecursive(tree: Tree) {
  if (tree) {
    r1.push(tree.val); // 在前面处理
    preOrderRecursive(tree.left);
    preOrderRecursive(tree.right);
  }
}
preOrderRecursive(treeRoot);
console.log("前序递归", r1.join("-")); // 0-1-3-4-2-5-6

// 中序递归
let r2 = [];
function inOrderRecursive(tree: Tree) {
  if (tree) {
    inOrderRecursive(tree.left);
    r2.push(tree.val); // 在中间处理
    inOrderRecursive(tree.right);
  }
}
inOrderRecursive(treeRoot);
console.log("中序递归", r2.join("-")); // 3-1-4-0-5-2-6

// 后序递归
let r3 = [];
function postOrderRecursive(tree: Tree) {
  if (tree) {
    postOrderRecursive(tree.left);
    postOrderRecursive(tree.right);
    r3.push(tree.val); // 在末尾处理
  }
}
postOrderRecursive(treeRoot);
console.log("后序递归", r3.join("-")); // 3-4-1-5-6-2-0

前中后栈

// 前序栈，根-左-右，考虑栈先入后出，所以要先放入右子树
function preOrderStack(tree: Tree) {
  if (!tree) {
    return [];
  }
  let stack = [tree]; // 节点栈
  let results = []; // 结果
  while (stack.length > 0) {
    let current = stack.pop();
    results.push(current.val);
    current.right && stack.push(current.right); // 先右后左
    current.left && stack.push(current.left);
  }
  return results;
}
console.log("前序栈", preOrderStack(treeRoot).join("-")); // 0-1-3-4-2-5-6

// 后序栈，左-右-根，可以认为是根-右-左的倒序
function postOrderStack(tree: Tree) {
  if (!tree) {
    return [];
  }
  let stack = [tree];
  let results = [];
  while (stack.length > 0) {
    let current = stack.pop();
    results.push(current.val);
    current.left && stack.push(current.left); // 先左后右
    current.right && stack.push(current.right);
  }
  return results.reverse(); // 倒序
}
console.log("后序栈", postOrderStack(treeRoot).join("-")); // 3-4-1-5-6-2-0

// 中序栈
function inOrderStack(tree: Tree) {
  if (!tree) {
    return [];
  }
  let stack = [];
  let results = [];
  let p = tree; // 遍历指针
  // 利用p=null的情况做跳过
  while (p || stack.length != 0) {
    if (p) {
      // 如果遍历指针存在，则加入栈，向左子树遍历
      stack.push(p);
      p = p.left;
    } else {
      // 如果遍历指针不存在，表示无左子树，输出出栈元素，并向右子树遍历
      p = stack.pop();
      results.push(p.val);
      p = p.right;
    }
  }
  return results;
}
console.log("中序栈", inOrderStack(treeRoot).join("-"));

补充：使用栈+状态标记来完成中序栈遍历

// 中序
// 状态机：每次循环，有2种状态：左子树入栈，当前节点出栈（并右子树入栈）
function inOrderStackStatus(tree: Tree) {
  if (!tree) {
    return [];
  }
  let stack = [tree]; // 栈
  let results = []; // 结果
  let status: "IN" | "OUT" = "IN"; // 状态
  while (stack.length != 0) {
    if (status === "IN") {
      // 入栈状态，放入栈顶元素的左子树
      let top = stack[stack.length - 1];
      if (top.left) {
        stack.push(top.left);
      } else {
        status = "OUT"; // 入栈失败，则修改状态为OUT，否则维持状态在IN
      }
    } else {
      // 出栈状态，输出栈顶元素，并放入栈顶元素的右节点
      let top = stack.pop();
      results.push(top.val);
      if (top.right) {
        stack.push(top.right);
        status = "IN"; // 成功入栈则修改状态为IN，否则维持状态在OUT
      }
    }
  }
  return results;
}
console.log("中序栈", inOrderStackStatus(treeRoot).join("-"));

参考资料

1. 1. 二叉树的中序遍历 - 力扣（LeetCode） [https://leetcode-cn.com/problems/binary-tree-inorder-traversal/]