leetcotsfe
作于

binary-tree-traversal

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

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

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

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

1
 
result
stack

类型定义

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
  },
}
更多推荐:

小计一次CLS优化

mui Grid 组件负 margin 和 object 元素影响 CLS 评分的分析
fehtmlcssmui

HTML 邮件需要注意的点

HTML 邮件需要注意的点及应当遵循的规范和禁忌
emailfehtml

mdx make blog better

为了支持 mdx, 做了很多妥协, 现在来试试吧
fereact