二叉树和多叉树的前序遍历：递归和迭代代码

遍历顺序：根 → 左 → 右

代码

递归

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
};