/**
 * @author wuze
 * @desc ...
 * @date 2021-07-20 22:56:06
 */
/*
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

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

输入：root = []
输出：[]

输入：root = [0]
输出：[0]
 */

public class 二叉树展开成链表_循环_114 {
    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) {
            //步骤：
            //1、把左子树接到对应改父节点的右子树
            //2、把刚刚被中间拦截的右子树接回刚插入的左子树的右边节点
            //3、然后将该节点的父节点的左子树置为null
            //4、遍历该树重复以上步骤
            while(root!=null){
                //如果左子树为null，继续遍历下一个节点
                if(root.left==null){
                    root=root.right;
                }else{
                    //先备份当前的右子树
                    TreeNode tmpRight = root.right;
                    //再将左子树接到右子树
                    root.right=root.left;

                    //然后将原来的右子树接回到左子树的最右节点
                    //（1）先备份左子树的父节点
                    TreeNode tmpLeft = root.left;
                    while(tmpLeft.right!=null){
                        tmpLeft = tmpLeft.right;
                    }
                    //（2）到达最右节点后，接入原来的右子树
                    tmpLeft.right = tmpRight;
                    //（3）再将原来的左子树置为null
                    root.left = null;
                }
            }

        }
    }
}