[数据结构与算法]leetcode 114. 二叉树展开为链表

题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

我的理解

按先序遍历串成链表
对于先序遍历的顺序来说，每一个节点的左节点一定是当前节点的下一节点。
那么，我们只要把左节点换到右节点就可以了。
可是，右节点的信息就会丢失。

那该怎么办呢？
我们只要提前把右子树转移到正确位置即可
当前节点的右节点的前驱节点一定在当前节点的左子树，有可能是最右节点，当然有可能是最右节点的左节点。

那我们现在把右子树提前挂到当前节点的左子树的最右节点上。
有人会问了，这不一定是前驱节点呀，这样写对吗？
不要怕，这样写对。当我们挂过去之后，我们在处理完一个节点，继续处理还会处理到这个最右节点，这时就会把右子树真正的前驱节点找出来。

看代码理解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){//左子节点不为空，将它转换到右节点（后驱节点）
                TreeNode next = cur.left;
                while(next.right != null){
                    next = next.right;
                }
                next.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}