中序遍历

1. 示例

输入: [1, 2, 3, null, null, 4]
   1
 /  \
2    3
    /
   4
输出: [2, 1, 4, 3]

2. 递归实现

function dfs(root) {
  if (!root) {
    return
  }
  dfs(root.left)
  console.log(root.val)
  dfs(root.right)
}

3. 非递归

function dfs(root) {
  const stack = []
  let cur = root
  while (cur || stack.length) {
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    cur = stack.pop()
    // 中序遍历
    console.log(cur.val)
    cur = cur.right
  }
}

4. 题目

• 二叉树的中序遍历