前序遍历

1. 示例

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

2. 递归实现

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

3. 非递归

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