114. 二叉树展开为链表

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

样例输入

示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [0]
输出：[0]

思路分析

对于二叉树类的题我们还是按照之前的思路来分析：

1. 可以通过遍历traverse一棵树来解决吗
2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值
3. 如果单独分离出每个节点，每个节点需要做什么

通过分析我们发现，将二叉树的节点转换成一条单链表，对于每个节点，都是将它的子树排列成一条链表，之后再与右侧合并，对于每一个节点都可以这样做，因此我们可以考虑使用递归的方法来实现
具体的将子节点合并成一条链的步骤：

• 将root.right指向左边的节点
• 将左子树中最大的节点的next指向root的右子树

之后便可以合并成一条链，重复上述步骤

参考代码

var flatten = function(root) {
    if(!root) return
    flatten(root.left)
    flatten(root.right)
    let leftChild = root.left
    let rightChild = root.right
    // 将右子树放到左子树下，左子树放到root下
    root.left = null
    root.right = leftChild
    // 现在的root.rigth指向之前的root.left,
    // 找到之前root.left的最大节点，也就是root.left的最右节点

    let p = root
    while(p.right) {
        p= p.right
    }
    p.right = rightChild
};