[数据结构与算法]【力扣刷题篇】之【二叉树展开成链表】

?hello，愿意点进来的小伙伴们，你们好呐！
? 🐻🐻系列专栏：【力扣刷题篇】
🐲🐲本篇内容：每日一题
🐯🐯作者简介:一名现大二的三非编程小白

二叉树展开为链表

链接: 二叉树展开为链表

思路：

这道题是想让我们将一颗二叉树以前序遍历的方式将其转化为一颗只有right节点的二叉树。
这道题我们的解题思路有两个思路：

思路1：

1. 我们可以先前序遍历这棵二叉树，并将每个节点存储在ArrayList中。
2. 然后遍历ArrayList，将其建成一颗只有right节点的二叉树，在该树上所有的left节点都为null

Java代码如下：

class Solution {
    public void flatten(TreeNode root){
        List<TreeNode> list = new ArrayList();
        preorderTraversal(root,list);

        int size = list.size();
        for(int i = 1;i < size;i++){
            TreeNode prev = list.get(i - 1);
            TreeNode cur = list.get(i);
            prev.left = null;
            prev.right = cur;
        }

    }
    //将树的节点都存储到list中
    public void preorderTraversal(TreeNode root, List<TreeNode> list){
        TreeNode cur = root;
        if(cur != null){
            list.add(cur);
            preorderTraversal(root.left,list);
            preorderTraversal(root.right,list);
        }
    }
}

思路2：

思路1的空间复杂度会达到O（N），那么我们还有别的思路减低空间复杂度吗？

1. 我们可以先定义cur指向root。
2. 然后用while循环判断cur是否为null。
3.在while中对cur的left节点进行判断，若不为null，则定义prev指向cur的left，next指向prev
4. 然后再用一个while循环，判断next的right是否为null，若不为null，则next指向next的right，直到next的right为null。
5. 然后next的right重新指向cur的right。cur的left不再指向树的节点，指向null。cur的right重新指向prev。
6.然后cur指向cur的right，继续重复while判断。

看到思路后可能还很难理解，现在我们来看看图解：

1.定义cur，next，prev

2.next找到最后为null的结点前。

3.将next的right指向cur的right

4.cur的lleft指向null

5.cur的left指向prev

6.cur指向cur的right

7.重新循环判断

8.

==9.最终就会将该树组成一棵新的树

Java代码如下：

class Solution {
    public void flatten(TreeNode root){
       TreeNode cur = root;
       while(cur != null){
           if(cur.left != null){
               TreeNode next = cur.left;
               TreeNode prev = next;
               while(prev.right != null){
                   prev = prev.right;
               }

               prev.right = cur.right;
               cur.left = null;
               cur.right = next;
           }
           cur = cur.right;
       }
    }
}