binary-tree-traversal

二叉树的先序、中序、后序遍历
从 leetcode Binary Tree Inorder Traversal 引申

所谓 先序、中序、后序，指的是遍历根节点的时机，

• 先序就是先遍历根节点（根左右）
• 中序就是把根节点放在中间（左根右）
• 后序就是后遍历根节点（左右根）

递归太简单了，就不说了，下面是一个关于循环遍历的演示 demo(代码在文章最后面)

类型定义

export interface TreeNode {
  val: number
  left: this | null
  right: this | null
}

export type OrderType = 'preorder' | 'inorder' | 'postorder'

type TraversalMap = Record<
  OrderType,
  <T extends TreeNode>(node: T | null) => T[]
>

递归遍历

export const RECURSIVE_TRAVERSAL: TraversalMap = {
  preorder(root) {
    if (!root) {
      return []
    }
    return [
      root,
      ...RECURSIVE_TRAVERSAL.preorder(root.left),
      ...RECURSIVE_TRAVERSAL.preorder(root.right),
    ]
  },

  inorder(root) {
    if (!root) {
      return []
    }
    return [
      ...RECURSIVE_TRAVERSAL.inorder(root.left),
      root,
      ...RECURSIVE_TRAVERSAL.inorder(root.right),
    ]
  },

  postorder(root) {
    if (!root) {
      return []
    }
    return [
      ...RECURSIVE_TRAVERSAL.postorder(root.left),
      ...RECURSIVE_TRAVERSAL.postorder(root.right),
      root,
    ]
  },
}

循环遍历

export const ITERATIVE_TRAVERSAL: TraversalMap = {
  preorder(root) {
    if (!root) {
      return []
    }
    type Node = typeof root
    const stack: Node[] = []
    const result: Node[] = []
    let cur: Node | null = root
    while (cur) {
      result.push(cur)
      if (cur.right) {
        stack.push(cur.right)
      }
      if (cur.left) {
        stack.push(cur.left)
      }
      cur = stack.pop() ?? null
    }
    return result
  },

  inorder(root) {
    if (!root) {
      return []
    }
    type Node = typeof root
    const stack: Node[] = []
    const result: Node[] = []
    let cur: Node | null = root
    while (cur || stack.length > 0) {
      while (cur) {
        stack.push(cur)
        cur = cur.left
      }
      const node = stack.pop()
      if (node) {
        result.push(node)
      }
      cur = node?.right ?? null
    }
    return result
  },

  postorder(root) {
    if (!root) {
      return []
    }
    type Node = typeof root
    const stack: Node[] = []
    const result: Node[] = []
    let cur: Node | null = root
    while (cur) {
      result.unshift(cur)
      if (cur.left) {
        stack.push(cur.left)
      }
      if (cur.right) {
        stack.push(cur.right)
      }
      cur = stack.pop() ?? null
    }
    return result
  },
}