来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

题目描述

给定一棵二叉树，将它展开为链表，要求如下：
1.开后的单链表应该同样为二叉树（TreeNode），right 子指针指向链表中下一个结点，而左子指针始终为 null；
2.展开后的单链表二叉树的先序遍历顺序相同。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

题目分析

下面提供两种方法：

• 前序遍历
• 前序遍历 + 放入链表同时（方法一的延伸）

代码实现

public class ZhanKaiLianBiao114 {

    public static void main(String[] args) {
        ZhanKaiLianBiao114 zhanKaiLianBiao114 = new ZhanKaiLianBiao114();
        /**
         *         1
         *    10      2
         *           3  9
         */
        TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9)));
        zhanKaiLianBiao114.flatten2(root);
    }


    /**
     * 【前序遍历 + 放入链表同时】
     * <p>
     * 时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历的同时对每个节点更新左右子节点的信息，更新子节点信息的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
     * <p>
     * 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈的大小，栈内的元素个数不会超过 n。
     *
     * @param root
     */
    public void flatten2(TreeNode root) {
        if(root == null){
            return;
        }

        // 栈，先进后出
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        TreeNode result = null;

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();

            if (result != null) {
                result.left = null;
                result.right = curr;
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
            result = curr;
        }
    }


    /**
     * 【前序遍历】
     * <p>
     * 时间复杂度：O(n)，其中 n是二叉树的节点数。前序遍历的时间复杂度是 O(n)O(n)O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
     * <p>
     * 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。
     *
     * @param root
     */
    public void flatten(TreeNode root) {

        List<TreeNode> list = new ArrayList<TreeNode>();
        // 前序遍历
        preOrder(root, list);
        System.out.println(list);

        for (int i = 1; i < list.size(); i++) {

            TreeNode result = list.get(i - 1);
            TreeNode curr = list.get(i);
            result.left = null;
            result.right = curr;
        }

        System.out.println(root);
    }

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

}

两种方法复杂度一致

• 时间复杂度：O(n)
• 空间复杂度：O(n)

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！