2021-02-11 114. 二叉树展开为链表

题目地址

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
 
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]

提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

思路

1. 对二叉树进行先序遍历，在遍历过程中创建新树，只进行右子树的创建，新树就是所要的结果。
2. 也可以将二叉树先序遍历结果存下来，一次性创建，这个并没有比前一种更优。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/11 9:00 下午
 */
public class Flatten {
    public static void main(String[] args) {
        int[] arr = {1,-1,2,3};
        NodeTree root = NodeTree.createTree(arr);
        NodeTree tmp = new NodeTree(-1);
//        flatten(root, tmp);
//        NodeTree newTree = tmp.getRight();
//        newTree.preOrder(newTree);
//        System.out.println();

//        tmp = new NodeTree(-1);
//        root = NodeTree.createTree(arr);
//        flattenV3(root, tmp, null);
//        root.preOrder(tmp.getRight());

//        root = NodeTree.createTree(arr);
//        flattenV2(root);
//        root.preOrder(root);
    }
    

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38 MB, 在所有 Java 提交中击败了38.69%的用户
     */
    private static void flatten(NodeTree root, NodeTree newTree) {
        if (root != null) {
            newTree.setRight(new NodeTree(root.getValue()));
            flatten(root.getLeft(), newTree.getRight());
            while (newTree.getRight() != null) {
                newTree = newTree.getRight();
            }
            flatten(root.getRight(), newTree);
        }
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了40.83%的用户
     * 内存消耗：38 MB, 在所有 Java 提交中击败了28.55%的用户
     */
    private static void flattenV2(NodeTree root) {
        List<NodeTree> queue = new ArrayList<>();

        doFlattenV2(root, queue);
        reDoTree(root, queue);
    }

    private static void reDoTree(NodeTree root, List<NodeTree> queue) {
        while (queue.size() > 0) {
            root.setRight(queue.remove(0));
            root.setLeft(null);
            root = root.getRight();
        }
    }

    private static void doFlattenV2(NodeTree root, List<NodeTree> queue) {
        if (root != null) {
            queue.add(root);
            doFlattenV2(root.getLeft(), queue);
            doFlattenV2(root.getRight(), queue);
        }
    }
}