二叉树展开为链表

LeetCode-114

// 队列解法 O(n)

var flatten = function(root) {
  let orderArr = [] // 队列
  function preorder(node) {
    if(node === null) return
    orderArr.push(node)
    preorder(node.left)
    preorder(node.right)
  }
  // 先序遍历节点
  preorder(root)

  // 右节点指向下一个节点，左节点指向null
  while(orderArr.length) {
    let node = orderArr.shift()
    node.right = orderArr[0] || null // 最后一个节点需指向null
    node.left = null
  }
  return root // 返回root
}