力扣hot100 114题二叉树展开为链表 打卡

力扣hot100 114题二叉树展开为链表 打卡

114. 二叉树展开为链表

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

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

解题思路：因为题目告诉我们是与二叉树的先序遍历顺序相同，所以我们可以先对二叉树进行先序遍历，用List存储节点。遍历完成之后，再通过一个虚拟结点依次给root的 rigth 赋值，root的left赋值null。代码及提交截图如下：  

class Solution {
    public void flatten(TreeNode root) {
        List list = new ArrayList();
        dfs(root,list);
        int len = list.size();
        TreeNode pre = root;
        for(int i = 1 ; i < len ; i++){
            pre.right = list.get(i);
            pre.left = null;
            pre = pre.right;
        }
    }
    private void dfs(TreeNode root,List list){
        if(root == null){
            return;
        }
        list.add(root);
        dfs(root.left,list);
        dfs(root.right,list);
        return;
    }
    
}

提交截图：

总结：还有一种方法是边改变边遍历，可以再学习学习。