94. 二叉树的中序遍历

94. 二叉树的中序遍历

递归

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

  const result = []

  let currentNode = root

  // 先处理左侧结点
  const leftResult = inorderTraversal(currentNode.left)

  result.push(...leftResult)

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

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

  return result
}

迭代

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

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

  while (currentRoot || stack.length) {
    // 处理左结点
    while (currentRoot) {
      // 先将根结点推入栈
      stack.push(currentRoot)
  
      // 然后遍历左结点
      currentRoot = currentRoot.left
    }

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

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

    // 处理右结点
    currentRoot = currentRoot.right
  }
}