二叉树的遍历

前序遍历(DFS深度优先)

• 根 -> 左子树 -> 右子树【先遍历根节点，再遍历左子树，再遍历右子树】

【需掌握递归与迭代两种方法】

leetcode-144

• 下图前序遍历结果：A (B D F E) (C G H I)

// 递归实现：O(n)
let res = []
let preorder = (root) => {
  if(root === null) return
  res.push(root.val) // 存储根节点值
  preorder(root.left) // 遍历左子树
  preorder(root.right) // 遍历右子树
}
preorder(root)

// 迭代实现【维护一个栈】
// 根 --> 左 --> 右
var preorderTraversal = function (root) {
  if (!root) return []
  let stack = [root]
  let res = []
  while (stack.length) {
    let node = stack.pop() // 栈顶取出一个
    res.push(node.val)
    if(node.right) stack.push(node.right) // 先将右子树压到栈底
    if(node.left) stack.push(node.left) // 左子树入栈
  }
  return res
}

中序遍历(DFS深度优先)

• 左子树 -> 根 -> 右子树

leetcode-94

• 下图中序遍历结果：(D B F E) A (G H C I)

// 递归实现：O(n)
let res = []
let inorder = (root) => {
  if(root === null) return
  inorder(root.left) // 遍历左子树
  res.push(root.val) // 没有左子树了则存储当前节点值
  inorder(root.right) // 遍历右子树
}
inorder(root)

// 迭代实现【维护一个栈】
const inorderTraversal = (root) => {
  let res = []
  let stack = []
  let node = root
  while(node || stack.length) {
    // 左子树先入栈
    while(node) {
      stack.push(node)
      node = node.left
    }
    node = stack.pop() // 取出栈顶元素
    res.push(node.val)
    node = node.right
  }
  return res
}

后序遍历(DFS深度优先)

• 左子树 -> 右子树 -> 根

leetcode-145

• 下图后序遍历结果：(D E F B) (H G I C) A

// 递归实现：O(n)
let res = []
let postorder = (root) => {
  if(root === null) return
  postorder(root.left) // 遍历左子树
  postorder(root.right) // 遍历右子树
  res.push(root.val) // 存储根节点值
}
postorder(root)

// 迭代实现【维护一个栈】
const postorderTraversal = (root) => {
  if(!root) return []
  const res = []
  const stack = [root]
  while(stack.length) {
    const node = stack.pop() // 取出栈顶节点
    res.unshift(node.val)
    if(node.left) stack.push(node.left)
    if(node.right) stack.push(node.right)
  }
  return res
}

层序遍历(BFS广度优先)

一层一层遍历 leetcode-102

• 下图层序遍历结果：[[1], [2, 3, 4], [5, 6, 7, 8], [9, 10]]

// 迭代实现【维护一个队列】
var levelOrder = function(root) {
  if(root === null) return []
  let res = []
  let queue = [root]
  while(queue.length) {
    let temp = [] // 存放每一层的val
    let queueLen = queue.length // 获取队列长度(该层有多少个就循环多少次)

    for(let i = 0; i < queueLen; i++) {
      let node = queue.shift()
      temp.push(node.val) // 将该层的val，依次push到temp
      if(node.left) queue.push(node.left) // 左子树先入队列
      if(node.right) queue.push(node.right) // 右子树次之
    }
    res.push(temp) // 循环一次队列，插入一个数组，用于存放层的每一个val
  }
  return res
}