114. 二叉树展开为链表

生活中可以没有诗歌，但不能没有诗意。

参考114. 二叉树展开为链表。

题目

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

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

• 展开后的单链表应该与二叉树 先序遍历 顺序相同。
  

  

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

解题思路

• 前序遍历：直接按前序遍历的顺序遍历树存储到队列中,然后依次相连。
• 递归：对于树的搜索优先考虑递归,展开左右子树后,相连。

前序遍历

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

    public void dfs(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            dfs(root.left, list);
            dfs(root.right, list);
        }
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数。
• 空间复杂度：O(n)。

递归

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left); // 先将左子树和右子树展开
        flatten(root.right);
        TreeNode left = root.left,right = root.right;
        root.left = null; // 将左子树置空，将右子树接到左子树的位置上
        root.right = left;
        while (root.right != null) root = root.right;  // 找到当前链表的末尾 
        root.right = right; // 将原来的右子树接在末尾
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数。
• 空间复杂度：O(1)。