二叉树刷题模板

深度优先：前序（中左右），中序（左中右），后序（左右中）

广度优先：层序（迭代法）

常见解法：递归法、迭代法

递归法

const preorderTraversal = function (root) {
  if (!root) return []
  let res = []
  const traversal = node => {
    res.push(node.val)
    node.left && traversal(node.left)
    node.right && traversal(node.right)
  }
  traversal(root)
  return res
}

const preorderTraversal = function (root) {
  if (!root) return []
  let res = []
  const traversal = node => {
    res.push(node.val)
    node.left && traversal(node.left)
    node.right && traversal(node.right)
  }
  traversal(root)
  return res
}

迭代法

前序遍历、后序遍历

const preorderTraversal = function (root) {
  let res = []
  let stack = [root]
  while (stack.length) {
    const node = stack.pop()
    if (node) {
      res.push(node.val) // 后序遍历只需要把这里改成shift
      // ['node', 'node.right', 'node.left'] // 优先取出队尾元素遍历
      // 先右后左
      node.right && stack.push(node.right)
      node.left && stack.push(node.left)
    }
  }
  return res
}

const preorderTraversal = function (root) {
  let res = []
  let stack = [root]
  while (stack.length) {
    const node = stack.pop()
    if (node) {
      res.push(node.val) // 后序遍历只需要把这里改成shift
      // ['node', 'node.right', 'node.left'] // 优先取出队尾元素遍历
      // 先右后左
      node.right && stack.push(node.right)
      node.left && stack.push(node.left)
    }
  }
  return res
}

中序遍历

const inorderTraversal = function (root) {
  let res = []
  let stack = []
  let cur = root
  while (stack.length || cur) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      cur = stack.pop()
      res.push(cur.val)
      // 理解这一步是关键，末端节点的right肯定为空
      // 那么进入下一轮循环的时候，cur依然为空
      // 弹出来的就是它的上一级节点了，继续进入到这个else块中
      cur = cur.right
    }
  }
  return res
}

const inorderTraversal = function (root) {
  let res = []
  let stack = []
  let cur = root
  while (stack.length || cur) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      cur = stack.pop()
      res.push(cur.val)
      // 理解这一步是关键，末端节点的right肯定为空
      // 那么进入下一轮循环的时候，cur依然为空
      // 弹出来的就是它的上一级节点了，继续进入到这个else块中
      cur = cur.right
    }
  }
  return res
}

层序遍历

const levelOrder = function (root) {
  if (!root) return []
  let result = []
  let queue = [root]
  while (queue.length) {
    // 保存当前层级的遍历结果
    let curLevel = []
    // 记录当前层级的长度
    let length = queue.length
    for (let i = 0; i < length; i++) {
      let node = queue.shift()
      curLevel.push(node.val)
      // 在上一层就记录好了下一层的结果，也就是说到了下一轮循环的时候，层的长度就已知了
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
    // 加入结果
    result.push(curLevel)
  }
  return result
}

const levelOrder = function (root) {
  if (!root) return []
  let result = []
  let queue = [root]
  while (queue.length) {
    // 保存当前层级的遍历结果
    let curLevel = []
    // 记录当前层级的长度
    let length = queue.length
    for (let i = 0; i < length; i++) {
      let node = queue.shift()
      curLevel.push(node.val)
      // 在上一层就记录好了下一层的结果，也就是说到了下一轮循环的时候，层的长度就已知了
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
    // 加入结果
    result.push(curLevel)
  }
  return result
}

层序遍历模板可以解决的问题：

层次遍历、右视图、层平均值、N 叉树层序、每个树行找最大值、最大深度、最小深度

二叉树刷题模板 ​

递归法 ​

迭代法 ​

层序遍历 ​

二叉树刷题模板

递归法

迭代法

层序遍历