二叉树 · 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
}

层序遍历

递归

const levelOrder = (root: TreeNode | null): number[][] => {
  const ans: number[][] = []
 
  const dfs = (node: TreeNode | null, depth: number) => {
    if (node == null) return null
    ans[depth] = (ans[depth] || []).concat(node.val)
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)
  }
  dfs(root, 0)
 
  return ans
}

迭代

const levelOrder = (root: TreeNode | null): number[][] => {
  if (root == null) return []
 
  const ans: number[][] = []
 
  const queue: TreeNode[] = [root]
  while (queue.length > 0) {
    const len = queue.length
    const tmp: number[] = []
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      tmp.push(node.val)
      if (node.left != null) queue.push(node.left)
      if (node.right != null) queue.push(node.right)
    }
    ans.push(tmp)
  }
 
  return ans
}

根据前、中、后遍历结果构建二叉树

前序&中序

const buildTree = (preorder: number[], inorder: number[]): TreeNode | null => {
  if (preorder.length == 0) return null
 
  const root_val = preorder[0]
  const root_index = inorder.indexOf(root_val)
 
  return new TreeNode(
    root_val,
    buildTree(preorder.slice(1, root_index + 1), inorder.slice(0, root_index)),
    buildTree(preorder.slice(root_index + 1), inorder.slice(root_index + 1))
  )
}

中序&后序

const buildTree = (inorder: number[], postorder: number[]): TreeNode | null => {
  if (postorder.length == 0) return null
 
  const root_val = postorder.at(-1)
  const root_index = inorder.indexOf(root_val)
 
  return new TreeNode(
    root_val,
    buildTree(inorder.slice(0, root_index), postorder.slice(0, root_index)),
    buildTree(inorder.slice(root_index + 1), postorder.slice(root_index, -1)),
  )
}

前序&后序

const buildTree = (preorder: number[], postorder: number[]): TreeNode | null => {
  if(preorder.length == 0) return null
 
  const [root_val, sub_root_val] = [preorder[0], preorder[1]]
  const sub_root_index = postorder.indexOf(sub_root_val)
 
  return new TreeNode(
    root_val,
    buildTree(preorder.slice(1, sub_root_index + 2), postorder.slice(0, sub_root_index + 1)),
    buildTree(preorder.slice(sub_root_index + 2), postorder.slice(sub_root_index + 1))
  )
}