给定一棵二叉树的根节点root请你将它展开为一个单链表。要求展开后的单链表同样使用TreeNode结构链表中每个节点的right指针指向“下一个”节点每个节点的left指针必须为空链表节点顺序与原二叉树的先序遍历​ 顺序完全相同。示例输入root [1,2,5,3,4,null,6]对应二叉树1 / \ 2 5 / \ \ 3 4 6先序遍历顺序1 - 2 - 3 - 4 - 5 - 6展开后1 \ 2 \ 3 \ 4 \ 5 \ 6输出结构可理解为[1,null,2,null,3,null,4,null,5,null,6]另一个例子输入root []输出[]输入root [1]输出[1]二、为什么这道题值得学习LeetCode 114 是二叉树操作中的经典题也是面试中经常出现的中等难度题目。它主要考察二叉树的先序遍历指针操作如何在遍历过程中修改树结构对递归和迭代两种写法的理解。很多同学第一眼看到“展开为链表”会想到先遍历一遍得到数组再重新连起来。这个思路是对的但还可以更优雅。这道题的核心本质是按照先序遍历的顺序把整棵树“拉平”成只有右子树的单链。所谓先序遍历根节点 - 左子树 - 右子树例如1 / \ 2 5 / \ \ 3 4 6先序遍历结果是1, 2, 3, 4, 5, 6所以展开后也必须是1 - 2 - 3 - 4 - 5 - 6并且所有left都要置为null。三、核心思想先序遍历 重构右链最直观的做法是先序遍历二叉树把访问到的节点值/节点本身存下来再按照顺序把它们用right指针串成链表每个节点的left置为null。例如原树先序1, 2, 3, 4, 5, 6构造链表1.right 2 2.left null 2.right 3 3.left null 3.right 4 ...最终得到1 - 2 - 3 - 4 - 5 - 6这种方法好理解适合面试时先写出基础版本。四、解题思路分析1. 先序遍历收集节点定义一个列表ListTreeNode list new ArrayList();通过递归先序遍历private void preorder(TreeNode root, ListTreeNode list) { if(root null) return; list.add(root); preorder(root.left, list); preorder(root.right, list); }遍历完成后list中就是按先序顺序排列的节点。2. 按顺序连接成右单链假设列表中有节点[1,2,3,4,5,6]那么for(int i 0; i list.size() - 1; i) { TreeNode cur list.get(i); TreeNode next list.get(i 1); cur.left null; cur.right next; }最后一个节点自然没有下一个节点它的right保持null即可同时最好也保证left null。五、代码实现先序遍历 重新连线class Solution { public void flatten(TreeNode root) { ListTreeNode list new ArrayList(); preorder(root, list); for(int i 0; i list.size() - 1; i) { TreeNode cur list.get(i); TreeNode next list.get(i 1); cur.left null; cur.right next; } // 如果树非空最后一个节点也确保 left null if(list.size() 0) { list.get(list.size() - 1).left null; } } private void preorder(TreeNode root, ListTreeNode list) { if(root null) { return; } list.add(root); preorder(root.left, list); preorder(root.right, list); } }这个方法逻辑清晰时间复杂度O(N)空间复杂度O(N)用于保存节点列表和递归栈。六、过程图解以这棵树为例1 / \ 2 5 / \ \ 3 4 6第一步先序遍历访问顺序1, 2, 3, 4, 5, 6收集节点list [1,2,3,4,5,6]第二步重新连接1.left null, 1.right 2 2.left null, 2.right 3 3.left null, 3.right 4 4.left null, 4.right 5 5.left null, 5.right 6 6.left null, 6.right null最终结构1 \ 2 \ 3 \ 4 \ 5 \ 6七、复杂度分析时间复杂度O(N)每个节点先序遍历访问一次后续连接也只遍历列表一次。空间复杂度O(N)主要开销list存储所有节点递归调用栈在最坏情况下例如链状树深度可达O(N)。八、另一种方法寻找前驱节点原地修改除了“先收集再连接”还有一种更省额外空间的思路。核心观察对于当前节点root如果它有左子树那么左子树的最右节点就是“左子树先序遍历的最后一个节点”这个最右节点的right应该接上当前节点的原右子树然后把当前节点的左子树整体移到右边当前节点left置为null。代码class Solution { public void flatten(TreeNode root) { TreeNode cur root; while(cur ! null) { if(cur.left ! null) { TreeNode pre cur.left; // 找到左子树的最右节点 while(pre.right ! null) { pre pre.right; } // 将原右子树接到左子树最右节点后面 pre.right cur.right; // 把左子树移动到右边 cur.right cur.left; // 左子树置空 cur.left null; } // 继续处理下一个右节点 cur cur.right; } } }这种方法不需要额外列表空间更优。九、两种方法比较方法思路时间复杂度空间复杂度特点先序遍历 列表重连收集节点后再串成右链O(N)O(N)好理解适合先写出版本找前驱节点原地修改利用左子树最右节点衔接右子树O(N)O(1) 额外空间更巧妙面试加分面试中建议先说出“先序遍历 重连”的直观解法再补充“原地修改”的优化解法。十、常见错误与避坑指南❌ 错误一只把右子树连起来忽略左子树例如原树1 / 2正确展开1 \ 2不能只保留原来的右链而要把左子树也接到右边。❌ 错误二没有把left置为null题目要求左子指针始终为 null即使某个节点没有右节点也要保证node.left null;否则不符合“右单链”的结构要求。❌ 错误三在遍历的同时直接修改指针导致丢失子树比如root.right root.left; root.left null;如果没有提前保存原右子树可能会丢掉右子树。所以原地修改时要先把原右子树接到左子树最右节点后面。十一、面试高频追问1. 为什么展开顺序必须是先序遍历题目要求展开后的单链表与二叉树先序遍历顺序相同。先序遍历定义就是根 - 左 - 右所以链表也必须按这个顺序连接。2. 能不能用后序遍历做可以变形但不如先序直观。如果只用后序遍历直接构造需要处理更多顺序问题。最常见、最自然的解法还是先序遍历或基于先序顺序的原地调整。3. 原地修改版本会不会破坏遍历不会因为它每次处理当前节点时先找到左子树最右节点把原右子树接过去再把左子树移到右边然后继续往右走。相当于一边调整一边保证后续节点仍然能被访问到。总结LeetCode 114 的核心思想是二叉树展开为链表 按先序遍历顺序把所有节点用right指针串起来并把left置为null。可以用先序遍历收集节点 - 重新连线快速写出正确解法。也可以用找左子树最右节点 - 原地调整指针优化空间复杂度。这道题不仅考察二叉树遍历还非常锻炼对树节点指针的操作能力。