Problem: 114. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

【LeetCode 热题 100】114. 二叉树展开为链表——（解法一）后序遍历+头插法

整体思路

这段代码同样旨在解决 “二叉树展开为链表” 的问题，即将二叉树原地转换成一个按前序遍历顺序串联的“链表”。与上一个“后序遍历+头插法”的版本不同，此版本采用的是一种 “分解问题” (Divide and Conquer) 的思想，通过递归函数返回子问题（子树）展开后的尾节点来辅助父问题的解决。

1. DFS函数的设计：

   • 该算法的核心是一个辅助函数 dfs(node)，它的设计目标是：
     a. 原地展开以 node 为根的子树。
     b. 返回这棵子树被展开成链表后的尾节点。

2. 分解与合并逻辑 (Divide and Conquer)：

   • 分解 (Divide)：对于当前节点 node，问题被分解为两个子问题：展开左子树和展开右子树。这是通过递归调用 leftTail = dfs(node.left) 和 rightTail = dfs(node.right) 来实现的。
     • leftTail 会接收到左子树展开后链表的尾节点。
     • rightTail 会接收到右子树展开后链表的尾节点。
   • 解决 (Conquer)：当两个子问题都解决后（即左右子树都已各自拉平），开始处理当前节点 node，将其与两个已拉平的子链表合并。
     • 合并的目标是形成 node -> (左子链表) -> (右子链表) 的结构。
     • if (leftTail != null): 这个判断检查是否存在左子树。
       • leftTail.right = node.right;: 这是最关键的一步。它将左子链表的尾部 (leftTail) 的 right 指针，连接到原先 node 的右子树（现在已经是右子链表的头部）。这就把左右两个链表串起来了。
       • node.right = node.left;: 将 node 的右指针指向其左孩子，即左子链表的头部。
       • node.left = null;: 将 node 的左指针置空。
     • 完成这三步后，以 node 为根的子树已经被成功展开。

3. 返回尾节点：

   • 在合并完成后，需要确定并返回当前整个大链表（node + 左子链表 + 右子链表）的尾节点。
   • 这个尾节点的位置有三种可能：
     a. 如果存在右子树，那么尾节点就是右子树的尾节点 (rightTail)。
     b. 如果不存在右子树但存在左子树，那么尾节点就是左子树的尾节点 (leftTail)。
     c. 如果左右子树都不存在，那么尾节点就是 node 本身。
   • return rightTail != null ? rightTail : leftTail != null ? leftTail : node; 这句三元表达式完美地实现了这个逻辑。

这个算法通过自底向上的方式，在每一层都完成子树的展开和连接，最终将整个树拉平。

完整代码

class Solution {/*** 将给定的二叉树原地展开为链表。* @param root 二叉树的根节点*/public void flatten(TreeNode root) {// 调用辅助的DFS函数，主函数不需要返回值dfs(root);}/*** 辅助DFS函数：原地展开以 node 为根的子树，并返回展开后链表的尾节点。* @param node 当前子树的根节点* @return 展开后链表的尾节点*/private TreeNode dfs(TreeNode node) {// 基线条件：如果节点为空，则没有什么可展开的，返回 null。if (node == null) {return null;}// 1. 分解：递归地展开左右子树，并获取它们展开后的尾节点。TreeNode leftTail = dfs(node.left);   // 展开左子树，获取左链表的尾TreeNode rightTail = dfs(node.right); // 展开右子树，获取右链表的尾// 2. 解决/合并：处理当前节点 node，将其与已展开的左右子链表连接。// 如果存在左子树（即左子链表），才需要进行连接操作。if (leftTail != null) {// a. 将左链表的尾部的 right 指针，指向右子链表的头部 (node.right)。leftTail.right = node.right;// b. 将 node 的右指针指向左子链表的头部 (node.left)。node.right = node.left;// c. 将 node 的左指针置空。node.left = null;}// 3. 返回当前已展开大链表的尾节点。// 优先级：右子树的尾 > 左子树的尾 > 当前节点本身。if (rightTail != null) {return rightTail;}if (leftTail != null) {return leftTail;}return node;}
}

时空复杂度

时间复杂度：O(N)

1. 节点访问：该算法通过DFS递归遍历了树中的每一个节点。每个节点被访问和处理一次。
2. 操作：在每个节点上，执行的都是常数时间的指针操作。
3. 综合分析：
   • 如果树中有 N 个节点，dfs 函数会被调用 N 次。
   • 因此，总的时间复杂度与节点数成正比，即 O(N)。

空间复杂度：O(H)

1. 主要存储开销：算法是原地修改，没有创建新的数据结构来存储节点。主要的额外空间开销来自于 递归调用栈。
2. 空间大小：递归调用的深度取决于树的高度 H。
   • 在最好的情况下（一个完全二叉树），树的高度 H 约为 log N，空间复杂度为 O(log N)。
   • 在最坏的情况下（一个极度倾斜的链状树），树的高度 H 等于 N，此时递归栈的深度也为 N，空间复杂度为 O(N)。

综合分析：
算法的辅助空间复杂度主要由递归栈的深度决定，即树的高度 H。因此，空间复杂度为 O(H)。在最坏情况下，H 可能为 N，所以最坏空间复杂度也可以表述为 O(N)。

参考灵神