Lstmxx的空间

二叉树的遍历方式

递归

遍历整个二叉树

function traverse(root: TreeNode) {
  // 前序遍历代码
  traverse(root.left)
  // 中序遍历代码
  traverse(root.right)
  // 后序遍历代码
}

迭代

前序

function preFor(root: TreeNode) {
  const nodeList = []
  const stack = []
  while(root !== null || stack.length > 0) {
    while(root !== null) {
      stack.push(root)
      //****** 前序遍历位置 ******/
      // todo
      /************************/
      root = root.left
    }
    while(root === null && stack.length > 0) {
      root = stack.pop().right
    }
  }
}

中序

function inFor(root: TreeNode) {
  const nodeList = []
  const stack = []
  while(root !== null || stack.length > 0) {
    while(root !== null) {
      stack.push(root)
      root = root.left
    }
    root = stack.pop()
    //****** 中序遍历位置 ******/
    // todo
    /************************/
    root = root.right
  }
}

后序

function postFor(root: TreeNode) {
  const nodeList = []
  const stack = []
  const pre: TreeNode = null
  while(root !== null || stack.length > 0) {
    while(root !== null) {
      stack.push(root)
      root = root.left
    }
    root = stack[stack.length - 1]
    if (root.right === null || root.right === pre) {
      pre = root
      //****** 后序遍历位置 ******/
      // todo
      /************************/
      root = null
    } else {
      root = root.right
    }
  }
}

快速排序 框架

function sort(nums: number[], lo: number, hi: number) {
  /****** 前序遍历位置 ******/
  // 通过交换元素构建分界点 p
  const p = partition(nums, lo, hi)
  /************************/
  sort(nums, lo, p - 1)
  sort(nums, p + 1, hi)
}

归并排序 框架

function sort(nums: number[], lo: number, hi: number) {
  const mid = parseInt((lo + hi) / 2)
  sort(nums, lo, mid)
  sort(nums, mid + 1, hi)
  /****** 后序遍历位置 ******/
  // 合并两个排好序的子数组
  merge(nums, lo, mid, hi)
  /************************/
}

层级遍历

function traverse(TreeNode root) {
  if (root === null) return
  const nodeQueList: TreeNode[] = []
  nodeQueList.push(root)
  while(nodeQueList.length > 0) {
    const cur = nodeQueList.shift()
    /* 层级遍历代码位置 */
    /*****************/
    if (cur.left !== null) {
      nodeQueList.push(cur.left)
    }
    if (cur.right !== null) {
      nodeQueList.push(cur.right)
    }
  }
}