Leetcode - using sequence traversal features first completed 114. The binary tree to the list

题目：114. 二叉树展开为链表
这道题很有意思,Because of the various recursion in the comment area, I really can't understand it,Until I saw a completed comment that exploits the binary tree features,Just imitate it yourself,Just record and share.

思路一：重新建树

思路：All nodes are recorded in a linked list,然后设置.Be sure to save the node here,Because this question requires modification of the originalroot,而不是创建新的节点.

public void flatten(TreeNode root) {
    
     //先序遍历+建树
        if(root==null) return ;
        List<TreeNode> buildList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
// in preorder 左右,So on the stack 右左
        //Because the middle is processed first
        while (!stack.isEmpty()) {
    
            TreeNode pop = stack.pop();
            buildList.add(pop);
            if (pop.right != null) {
    
                stack.push(pop.right);
            }
            if (pop.left != null) {
    
                stack.push(pop.left);
            }
        }
        for (int i = 0; i < buildList.size()-1; i++) {
    
            buildList.get(i).left=null;
            buildList.get(i).right=buildList.get(i+1);
        }
        buildList.get(buildList.size()-1).left=null;
        buildList.get(buildList.size()-1).right=null;
    }

思路二：Take advantage of the preorder traversal feature

The method above requires extra space,This space complexity is O（1）

思路：Connect the current left subtree to the right,Then the first left subtree to be found、Then find the predecessor node of the right subtree,Connect the right subtree to the predecessor,Then move the whole left subtree to the right subtree.
听起来有点绕,来个例子,cur表示当前处理的节点,right_pre表示curThe predecessor of the right subtree
Take the graph in the example as an example,从根节点开始

1. cur = 1
   找到cur.left的最右节点right_pre,也就是4,然后把cur.right 接到right_pre后面.再把cur.left接到cur的右边
   处理完了之后：
   
   然后cur = cur.right,Why do you have the confidence to do so,因为curThe ones on the left have been moved to the right,And it is moved according to the preorder traversal,So just look to the right.

2. cur=2
   将4 接到 3 后面,3 再接到2后面,就能得到
   

But keep going to the right,See if there are any unhandled left children.

代码：

public void flatten(TreeNode root) {
    
       TreeNode cur = root;
        while ( cur!=null ){
    
            //in the pre-order table,找到当前节点的下一个节点
            TreeNode right_pre = cur.left;
            //找到cur.right的前一个,也就是左子树的最右节点
            while (right_pre!=null && right_pre.right != null ){
    
                right_pre = right_pre.right;
            }
            //拼接操作
            if(right_pre!=null){
    
                right_pre.right=cur.right;
                //Then connect the whole left side to the right side
                cur.right=cur.left;
                cur.left=null;
            }
            //继续寻找下一个
            cur = cur.right;
        }
    }