遍历顺序:根 → 左 → 右

二叉树的前序遍历顺序图示

代码

递归

const preorderTraversal = root => {
  return root ? [root.val].concat(preorderTraversal(root.left),preorderTraversal(root.right)) : []
}

迭代


const preorderTraversal = root => {
  if (root === null) return []
  const stack = [root], r = []
  while (stack.length) {
    const n = stack.pop()
    r.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return r
}

测试

输入:[0,1,2,3,4,5]
输出:[0,1,3,4,2,5]

例题

144. 二叉树的前序遍历

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

答案

代码如上

589. N 叉树的前序遍历

给定一个 n 叉树的根节点 root ,返回 其节点值的 前序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null 分隔(请参见示例)。

答案

递归
var preorder = function(root) {
  const r = []
  const d = n => {
    if (n === null) return
    r.push(n.val)
    const len = n.children.length
    for (let i = 0; i < len; i++) {
      d(n.children[i])
    }
  }
  d(root)
  return r
};
迭代
var preorder = function(root) {
  if (root === null) return []
  const stack = [root], r = []
  while (stack.length) {
    const n = stack.pop()
    r.push(n.val)
    for (let i = n.children.length; i--;) {
      stack.push(n.children[i])
    }
  }
  return r
};

255. 验证前序遍历序列二叉搜索树

给定一个 无重复元素 的整数数组 preorder , 如果它是以二叉搜索树的先序遍历排列 ,返回 true 。

答案

单调栈

顺序遍历:根→左→不能小于

var verifyPreorder = function(preorder) {
  const n = preorder.length, stack = []
  let root = Number.MIN_SAFE_INTEGER
  for (let i = 0; i < n; i++) {
    if (preorder[i] < root) return false
    while (stack.length && stack[stack.length - 1] < preorder[i]) {
      root = stack.pop()
    }
    stack.push(preorder[i])
  }
  return true
};

代码
JavaScript 优先队列代码:支持自定义排序
JavaScript 实现优先队列的代码,自定义排序(最小堆、最大堆都可以),支持数组、矩阵、对象
代码
JavaScript 最大堆(大根堆、大顶堆)代码
最大堆,又称大根堆,大顶堆,JavaScript 实现大根堆的代码。
代码
广度优先搜索:求解《429. N 叉树的层序遍历》和 《675. 为高尔夫比赛砍树》
广度优先搜索,求解《429. N 叉树的层序遍历》和 《675. 为高尔夫比赛砍树》