【二叉树】Leetcode 114. 二叉树展开为链表【中等】

二叉树展开为链表

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

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

示例1：

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

解题思路

展开二叉树为单链表可以使用前序遍历的方式来实现。

• 1、对于当前节点，首先将其左子树展开为单链表，并将左子树的最右节点连接到当前节点的右子树上。
• 2、然后将当前节点的右子树展开为单链表。
• 3、如果左子树不为空，将当前节点的右子树设为展开后的左子树；否则，将左子树设为右子树。

Java实现

public class FlattenBinaryTreeToLinkedList {

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

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        flattenHelper(root);
    }

    private TreeNode flattenHelper(TreeNode node) {
        if (node == null) {
            return null;
        }
        //    1
        //   / \
        //  2   5
        // / \   \
        //3   4   6
        // 把右子树放到左子树的右子树上
        //      1
        //     / \
        //    2   5
        //   / \   \
        //  3   4   6
        //   \
        //    4
        //把左子树移到右子树下
        //      1
        //     / \
        //    2   5
        //     \   \
        //      3   6
        //       \
        //        4
        //把右子树移到左子树的右子树下
        //      1
        //     / \
        //    2   5
        //     \   \
        //      3   6
        //       \
        //        4
        //         \
        //          5
        //           \
        //            6
        //把左子树替换到右子树上
        //      1
        //       \
        //        2
        //         \
        //          3
        //           \
        //            4
        //             \
        //              5
        //               \
        //                6
        //链表符合前序遍历了，并且左子树全为null
        TreeNode leftTail = flattenHelper(node.left);
        TreeNode rightTail = flattenHelper(node.right);


        if (leftTail != null) {
            // 把右子树放到左子树的右子树上
            leftTail.right = node.right;
            // 把（带有右子树的）左子树赋给右子树
            node.right = node.left;
            // 右子树清空
            node.left = null;
        }

//        在这里，rightTail 的优先级最高，然后是 leftTail，最后是 node。
//        这确保了在递归的过程中，当前子树展开后的链表的尾节点是按照
//        右子树、左子树、当前节点的顺序确定的。
//        这样的顺序保证了链表的正确连接，即右子树的尾部接在左子树的尾部，
//        而左子树的尾部接在当前节点的右侧。这样展开后的链表顺序符合二叉树的先序遍历。
        return (rightTail != null) ? rightTail : (leftTail != null) ? leftTail : node;
    }

    // 示例测试
    public static void main(String[] args) {
        FlattenBinaryTreeToLinkedList solution = new FlattenBinaryTreeToLinkedList();

        // 构造示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        // 调用展开方法
        solution.flatten(root);

        // 打印展开后的链表
        TreeNode current = root;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.right;
        }
    }
}

时间空间复杂度

• 时间复杂度：O(n)，其中n是二叉树中的节点数，每个节点都需要访问一次。
• 空间复杂度：O(h)，递归调用栈的深度为树的高度。