LeetCode 114. 二叉树展开为链表

题目描述

难度：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
};