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]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

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

二、解题思路

将根节点的左子树和右子树拉平。
将拉平后的左子树作为右子树，将原来的右子树接到当前右子树的末端。

三、具体代码

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        root.right = left;
        
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

对于每个节点，我们首先递归地展平其左子树，这需要 O(left) 的时间，其中 left 是左子树中的节点数。
然后，我们递归地展平其右子树，这需要 O(right) 的时间，其中 right 是右子树中的节点数。
最后，我们将左子树移动到右子树的位置，并找到新的右子树的末端以连接原始的右子树。这个操作需要 O(left) 的时间。
因此，对于每个节点，我们在最好情况下（没有子节点）需要 O(1) 时间，在最坏情况下（左右子树都有）需要 O(left + right) 时间。
由于每个节点只被访问一次，整体时间复杂度是 O(n)，其中 n 是树中节点的总数。

2. 空间复杂度

空间复杂度主要取决于递归栈的深度，这通常与树的高度成正比。
在最坏的情况下，树完全不平衡，例如每个节点都只有左子节点，递归栈的深度将是 O(n)，其中 n 是树中节点的总数。
在最好的情况下，树是完全平衡的，递归栈的深度将是 O(log n)。
因此，空间复杂度在最坏情况下是 O(n)，在最好情况下是 O(log n)。

五、总结知识点

递归：这是一种常用的算法设计技巧，用于将复杂问题分解为更小的子问题。在这个问题中，我们使用递归将树的展平问题分解为子树的展平问题。
二叉树遍历：代码中隐式地使用了先序遍历（根-左-右）的顺序来展平二叉树。这是通过递归调用 flatten(root.left) 和 flatten(root.right) 实现的。
链表操作：展平二叉树的过程中，我们需要将左子树转换为链表，并将其连接到根节点的右侧，然后将原始的右子树连接到转换后的左子树的末端。这涉及到链表的基本操作，如节点的移动和连接。
指针操作：在 Java 中，我们使用 TreeNode 类型的变量来操作树节点。这些变量实际上是指向树中节点的指针。代码中使用了这些指针来修改节点的左右子节点。
边界条件处理：代码中首先检查 root 是否为 null，这是递归算法的边界条件。如果 root 为 null，则直接返回，不再进行递归。
引用传递：在 Java 中，对象是通过引用传递的。这意味着当我们在递归调用中传递 root.left 和 root.right 时，我们实际上是在传递对树节点对象的引用。因此，在递归调用中对这些节点所做的任何修改都会反映到原始树上。
循环结构：在将左子树移动到右子树位置后，我们使用了一个循环结构来找到新的右子树的末端，以便将原始的右子树连接起来。