一天一大 leet(二叉树展开为链表)难度:中等-Day20200802

    1
   / \
  2   5
 / \   \
3   4   6

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  // 特殊情况：传入的二叉树为空直接返回
  if (!root || root.length === 0) {
    return root
  }

  let list = []
  helper(root)
  //  遍历所有节点
  for (let i = 0; i < list.length - 1; i++) {
    let node = list[i],
      nextNode = list[i + 1]
    node.left = null
    node.right = nextNode
  }

  // 收集节点
  function helper(node) {
    if (node !== null) {
      list.push(node)
      helper(node.left)
      helper(node.right)
    }
  }
}

    1
   / \
  2   5
 / \   \
3   4   6
----------------------=>
    1
     \
      2
     / \
    3   4
         \
          5
           \
            6
----------------------=>
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

var flatten = function (root) {
  // 特殊情况：传入的二叉树为空直接返回
  if (!root || root.length === 0) {
    return root
  }
  function helper(node) {
    if (node !== null) {
      // 当前节点右侧节点
      let right = node.right
      // 将左节点放置到右节点  清除左节点，
      node.right = node.left
      node.left = null
//  遍历当前节点原左节点的右节点的根节点，使其余当前节点right节点连接
      let rightEnd = node
      while (rightEnd.right) {
        rightEnd = rightEnd.right
      }
      rightEnd.right = right
      // 右侧拼接的还有分支继续拼接
      helper(node.right)
    }
  }
  helper(root)
}