原文：114. 二叉树展开为链表(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0114/

题目：

难度：Middle

相关话题：树、深度优先搜索

给定一个二叉树，原地 将它展开为链表。

例如，给定二叉树

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

思路：

对于每个root节点，先将它的左子树和右子树分别保存为l和r；

接着继续flatten它的左子树，将flatten(l)的结果作为root的新的右子树，因为flatten(l)已经是一个平铺的树，因此可以沿着它的右子树一直找到最后一个节点node，然后将root原来的右子树r，作为node的右子树连接起来。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
  if(!root)return null
  let l=root.left,
      r=root.right
  root.left=null
  root.right=flatten(l)
  let node=root
  while(node.right)node=node.right
  node.right=flatten(r)
  return root
};