114.二叉树转化为链表

例如，给定二叉树

1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
// 前序遍历将所有节点塞入数组，遍历数组，让每个节点的left变成null right指向下一个节点
var flatten = function(root) {
    const list = [];
    pre(root, list);
    for (let i = 0; i < list.length - 1; i++) {
      list[i].left = null;
      list[i].right = list[i + 1];
    }
    return list[0];
};
function pre(root, list) {
  if (!root) {
    return;
  }
  list.push(root);
  pre(root.left, list);
  pre(root.right, list);
}

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
// 1.将一个节点的左右子树转换为单链表 2.将右子树插入到左子树的末尾 3，左子树变成右子树 4.左子树置为null
var flatten = function(root) {
    if (root === null) {
      return;
    }
      // 第1步
    flatten(root.left);
    flatten(root.right);
      // 左子树为null就不需要处理了
    if (root.left === null) {
      return;
    }
      //第2步
    let end = root.left;
    while(end && end.right) {
      end = end.right;
    }
    end.right = root.right
      //第3 第4步
    root.right = root.left;
    root.left = null;
    return root;
};