SkyBlog

二叉树

二叉树的遍历算法

节点的结构如下,以力扣为标准

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val == undefined ? 0 : val)
    this.left = (left == undefined ? null : left)
    this.right = (right == undefined ? null : right)
  }
}

前序遍历

递归

const preorderTraversal = (root: TreeNode | null): number[] => {
  if (root == null) return []
  return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)]
}

迭代

const preorderTraversal = (root: TreeNode | null): number[] => {
  const ans: number[] = []

  const stack: TreeNode[] = [root]
  while (stack.length > 0) {
    const node = stack.pop()
    if (node == null) continue
    ans.push(node.val)
    stack.push(node.right)
    stack.push(node.left)
  }

  return ans
}

中序遍历

递归

const inorderTraversal = (root: TreeNode | null): number[] => {
  if (root == null) return []
  return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
}

迭代

const inorderTraversal = (root: TreeNode | null): number[] => {
  const ans: number[] = []

  const stack: TreeNode[] = []
  let cur: TreeNode | null = root
  while (stack.length > 0 || cur != null) {
    if (cur != null) {
      stack.push(cur)
      cur = cur.left
    } else {
      cur = stack.pop()
      ans.push(cur.val)
      cur = cur.right
    }
  }

  return ans
}

后序遍历

递归

const postorderTraversal = (root: TreeNode | null): number[] => {
  if (root == null) return []
  return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
}

迭代

const postorderTraversal = (root: TreeNode | null): number[] => {
  const ans: number[] = []

  const stack: TreeNode[] = [root]
  while (stack.length > 0) {
    const node = stack.pop()
    if (node == null) continue
    ans.unshift(node.val)
    stack.push(node.left)
    stack.push(node.right)
  }

  return ans
}