My Muri Life

切换主题

本页目录

二叉树的遍历 ​

二叉树节点结构：

JavaScript
class TreeNode {
  constructor(val, left, right) {
    this.val = val
    this.left = left
    this.right = right
  }
}

递归遍历 ​

递归遍历二叉树的时间复杂度：O(n)；空间复杂度：O(n)。

前序遍历 ​

节点访问顺序： 根 -> 左 -> 右。

JavaScript
const preorder = (root, ret = []) => {
  if (!root) return ret
  ret.push(root.val)
  preorder(root.left, ret)
  preorder(root.right, ret)
  return ret
}

中序遍历 ​

节点访问顺序： 左 -> 根 -> 右。

JavaScript
const inorder = (root, ret = []) => {
  if (!root) return ret
  inorder(root.left, ret)
  ret.push(root.val)
  inorder(root.right, ret)
  return ret
}

后序遍历 ​

节点访问顺序： 左 -> 右 -> 根。

JavaScript
const postorder = (root, ret = []) => {
  if (!root) return ret
  postorder(root.left, ret)
  postorder(root.right, ret)
  ret.push(root.val)
  return ret
}

迭代遍历 ​

迭代遍历，即模拟后进（Array#push） 先出（Array#pop）的栈数据结构。
时间复杂度：O(n)；空间复杂度：O(n)。

前序遍历 ​

节点访问顺序： 根 -> 左 -> 右；
节点压栈顺序： 右 -> 左 -> 根。

JavaScript
const preorder = (root, ret = []) => {
  if (!root) return ret
  const stack = [root]
  while (stack.length) {
    // ==>节点出栈时即为操作时间点
    const node = stack.pop()
    // <==
    if (!node) { // node == null时，即标记节点
      ret.push(stack.pop().val)
      continue
    }
    node.right && stack.push(node.right)
    node.left && stack.push(node.left)
    stack.push(node, null)
  }
  return ret
}

中序遍历 ​

节点访问顺序： 左 -> 根 -> 右；
节点压栈顺序： 右 -> 根 -> 左。

JavaScript
const inorder = (root, ret = []) => {
  if (!root) return ret
  const stack = [root]
  while (stack.length) {
    // ==>节点出栈时即为操作时间点
    const node = stack.pop()
    // <==
    if (!node) { // node == null时，即标记节点
      ret.push(stack.pop().val)
      continue
    }
    node.right && stack.push(node.right)
    stack.push(node, null)
    node.left && stack.push(node.left)
  }
  return ret
}

后序遍历 ​

节点访问顺序： 左 -> 右 -> 根；
节点压栈顺序： 根 -> 右 -> 左。

JavaScript
const postorder = (root, ret = []) => {
  if (!root) return ret
  const stack = [root]
  while (stack.length) {
    // ==>节点出栈时即为操作时间点
    const node = stack.pop()
    // <==
    if (!node) { // node == null时，即标记节点
      ret.push(stack.pop().val)
      continue
    }
    stack.push(node, null)
    node.right && stack.push(node.right)
    node.left && stack.push(node.left)
  }
  return ret
}

层序遍历 ​

模拟先进（Array#push） 先出（Array#shift）的队列数据结构。

每层节点访问顺序： 左 -> 右；
每层节点入队顺序： 左 -> 右；
每层节点入队顺序： 左 -> 右。

JavaScript
const levelorder = (root, ret = []) => {
  if (!root) return ret
  const queue = [root]
  while (queue.length) {
    let [len, lvNodes] = [queue.length, []]
    while (len--) {
      // ==>节点出队时即为操作时间点
      const node = queue.shift()
      // <==
      lvNodes.push(node.val) // 出队时保存节点值
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
    ret.push(lvNodes)
  }
  return ret
}

Morris遍历 ​

Morris遍历二叉树的时间复杂度：O(n)；空间复杂度：O(1)。

遍历过程描述：

当前节点curr，一开始来到整棵树的头节点curr = root，若当前节点不为空curr != null:

  1. 若当前节点无左树curr.left == null，当前节点直接向右移动curr = curr.right；

  2. 若当前节点有左树curr.left != null，找到当前节点左树的最右节点mostRight:

    1. 若最右节点的右指针为空mostRight.right == null，将最右节点的右指针指向当前节点mostRight.right = curr，然后当前节点向左移动curr = curr.left；
    2. 若最右节点的右指针指向当前节点mostRight.right === curr，将最右节点的右指针置空mostRight.right = null，然后当前节点向右移动curr = curr.right。

Morris序 ​

JavaScript
const morris = root => {
  if (!root) return
  let [curr, mostRight] = [root, null]
  while (curr != null) {  // 迭代至curr为空
    mostRight = curr.left  // 判断curr有无左树
    if (mostRight != null) {  // 情况2：当前节点有左树
      // 找到左树的真实最右节点
      while (mostRight.right != null && mostRight.right != curr) {
        mostRight = mostRight.right
      }
      if (mostRight.right == null) {  // 情况2.1
        mostRight.right = curr
        curr = curr.left
        continue
      } else {  // 情况2.2
        mostRight.right = null
        // curr = curr.right
        // continue
      }
    }
    curr = curr.right  // 情况1：当前节点无左树，curr右移
  }
}

前序遍历 ​

节点第一次被遍历到时，即为前序。

JavaScript
const morrisPreorder = (root, ret = []) => {
  if (!root) return ret
  let [curr, mostRight] = [root, null]
  while (curr) {
    mostRight = curr.left
    if (mostRight) {
      while (mostRight.right && mostRight.right != curr) {
        mostRight = mostRight.right
      }
      if (mostRight.right == null) {
        mostRight.right = curr
        ret.push(curr.val)  // 节点第一次被遍历到
        curr = curr.left
        continue
      } else {
        mostRight.right = null
      }
    } else {
      ret.push(curr.val)  // 节点第一次被遍历到
    }
    curr = curr.right
  }
  return ret
}

中序遍历 ​

节点发生右移，即节点第二次被遍历到时即为中序。

JavaScript
const morrisInorder = (root, ret = []) => {
  if (!root) return ret
  let [curr, mostRight] = [root, null]
  while (curr) {
    mostRight = curr.left
    if (mostRight) {
      while (mostRight.right && mostRight.right != curr) {
        mostRight = mostRight.right
      }
      if (mostRight.right == null) {
        mostRight.right = curr
        curr = curr.left
        continue
      } else {
        mostRight.right = null
      }
    }
    ret.push(curr.val)  // 节点右移，即当前节点第二次被遍历到
    curr = curr.right
  }
  return ret
}

后序遍历 ​

后序遍历相较于前序遍历与中序遍历，稍微麻烦一点！

有左树的节点第二次被遍历到时逆序存储左树的右边界。

JavaScript
// 辅助函数：反转左树右边界，即反转链表
const reverseRB = node => {
  let [prev, next] = [null, null]
  while (node) {
    next = node.right
    node.right = prev
    prev = node
    node = next
  }
  return prev
}
// 辅助函数：逆序存储
const postStorage = (node, store = []) => {
  const root = reverseRB(node)
  let curr = root
  while (curr) {
    store.push(curr.val)
    curr = curr.right
  }
  reverseRB(root)
}
const morrisPostorder = (root, ret = []) => {
  if (!root) return ret
  let [curr, mostRight] = [root, null]
  while (curr) {
    mostRight = curr.left
    if (mostRight) {
      while (mostRight.right && mostRight.right != curr) {
        mostRight = mostRight.right
      }
      if (mostRight.right == null) {
        mostRight.right = curr
        curr = curr.left
        continue
      } else {
        mostRight.right = null
        postStorage(curr.left, ret)  // 有左树的节点第二次被遍历到
      }
    }
    curr = curr.right
  }
  postStorage(root, ret)  // 整个树的右边界
  return ret
}

数据结构应用 ​

leetcode
  1. 144. 二叉树的前序遍历
  2. 94. 二叉树的中序遍历
  3. 145. 二叉树的后序遍历
  4. 102. 二叉树的层序遍历