94. 二叉树的中序遍历 🟩

题目

LeetCode 简单

题目

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

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

题解

方法：递归

递归 O(n) O(n)

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

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

方法：迭代

栈 O(n) O(n)

function inorderTraversal(root) {
  let res = []
  let stack = []
  let p = root
  while (stack.length || p) {
    // 一路向左，把左子树全部压入栈
    while (p) {
      stack.push(p)
      p = p.left
    }

    console.log('stack', JSON.stringify(stack.map(i => i.val)))

    // 当左边到底了，弹出栈顶元素（最左边的叶子节点）
    const node = stack.pop()
    res.push(node.val)

    // 然后转向右子树
    p = node.right
  }
  return res
}

// 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// 构建一棵测试用的二叉树
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7
const root = new TreeNode(1)
root.left = new TreeNode(2, new TreeNode(4), new TreeNode(5))
root.right = new TreeNode(3, new TreeNode(6), new TreeNode(7))

console.log('🌰', inorderTraversal(root))

执行结果

stack [1,2,4]
stack [1,2]
stack [1,5]
stack [1]
stack [3,6]
stack [3]
stack [7]
🌰 [4,2,5,1,6,3,7]

本页目录