zhangdizhangdi

144.二叉树的前序遍历

题目

LeetCode 简单

题目

给定一个二叉树的根节点 root ，返回 它的 前序 遍历 。

示例：
输入：root = [1,null,2,3]
输出：[1,2,3]

题解

方法：递归

递归 O(n) O(n)

ts
function preorderTraversal(root: TreeNode | null): number[] {
  let res = []
  if (root) {
    const preorder = (node: TreeNode) => {
      res.push(node.val)
      if (node.left) preorder(node.left)
      if (node.right) preorder(node.right)
    }
    preorder(root)
  }
  return res
}

const tree = new Tree([3, 9, 20, null, null, 15, 7, 14, 13])
console.log('🌰', tree)
console.log('🌰', preorderTraversal(tree.root))

方法：迭代

栈 O(n) O(n)

ts
function preorderTraversalUseStack(root: TreeNode | null): number[] {
  let res = []
  if (root) {
    let stack = [root]
    while (stack.length) {
      console.log('stack', JSON.stringify(stack.map(i => i.val)))

      const node = stack.pop()
      res.push(node.val)
      if (node.right) stack.push(node.right)
      if (node.left) stack.push(node.left)
    }
  }
  return res
}

const tree = new Tree([3, 9, 20, null, null, 15, 7, 14, 13])
console.log('🌰', tree)
console.log('🌰', preorderTraversalUseStack(tree.root))