144. 二叉树的前序遍历

144. 二叉树的前序遍历

递归

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) {
    return []
  }

  const result = []

  let currentNode = root

  // 先处理当前结点
  result.push(currentNode.val)

  // 再处理左侧结点
  const leftResult = preorderTraversal(currentNode.left)

  result.push(...leftResult)

  // 然后处理右侧结点
  const rightResult = preorderTraversal(currentNode.right)
  result.push(...rightResult)

  return result
}

迭代

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) {
    return []
  }

  const result = []
  const stack = []
  let currentRoot = root

  while (currentRoot || stack.length) {
    // 处理左结点
    while (currentRoot) {
      // 先将根结点推入栈
      stack.push(currentRoot)

      // 前序遍历，在左结点处理前取值
      result.push(currentRoot.val)

      // 然后遍历左结点
      currentRoot = currentRoot.left
    }

    // 回到根结点
    // 从栈中将根结点取出
    currentRoot = stack.pop()

    currentRoot = currentRoot.right
  }

  return result
}