二叉树展开为链表

怎样从“标准样例原地展开为前序右链 1→2→3→4→5→6，所有 Left 为 nil。”推导出 二叉树 · 原地展开，并证明每次状态变化都不会漏掉答案？

中心结论：O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。

给定一个二叉树，原地将它展开为链表。

在本站主例中，标准样例原地展开为前序右链 1→2→3→4→5→6，所有 Left 为 nil。

算法最终需要得到或观察：1→2→3→4→5→6 右链。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 cur、pre、oldRight 三指针。
3. 3转移每一步按照 O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。
4. 4收尾读取 1→2→3→4→5→6 右链。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：cur、pre、oldRight 三指针。

要求把二叉树“打平”，按照先根遍历的顺序，把树的结点都放在右结点中。 按照递归和非递归思路实现即可。 递归的思路可以这么想：倒序遍历一颗树，即是先遍历右孩子，然后遍历左孩子，最后再遍历根节点。

1 / \ 2 5 / \ \ 3 4 6 ----------- pre = 5 cur = 4

1 / 2 / \ 3 4 \ 5 \ 6 ----------- pre = 4 cur = 3

1 / 2 / 3 \ 4 \ 5 \ 6 ----------- cur = 2 pre = 3

1 / 2 \ 3 \ 4 \ 5 \ 6 ----------- cur = 1 pre = 2

1 \ 2 \ 3 \ 4 \ 5 \ 6

可以先仿造先根遍历的代码，写出这个倒序遍历的逻辑：

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

实现了倒序遍历的逻辑以后，再进行结点之间的拼接：

private TreeNode prev = null;

public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root; }

O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。

执行过程中持续维护：cur、pre、oldRight 三指针。

正确性依赖以下不变量：不是新建链表,原地改指针;已处理前缀形成正确前序右链;最终所有 Left=nil。

面试时可以压缩为：O(1) 原地:找 pre,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil;时间 O(n) 空间 O(1)。

落到当前题，执行机制可以压缩为：O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入标准样例原地展开为前序右链 1→2→3→4→5→6，所有 Left 为 nil。 因为：O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。
2. 2递归栈:根-左-右从根开始 DFS。 因为：前序第一个输出根。
3. 3访问结点 2记录当前结点。 因为：根在子树之前被访问。
4. 4访问结点 3记录当前结点。 因为：根在子树之前被访问。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6访问结点 5记录当前结点。 因为：根在子树之前被访问。
7. 7前序结果: 1 → 2 → 3 → 4 → 5 → 6栈空,输出完整。 因为：O(n) 访问每个结点一次。
8. 8收尾与复杂度1→2→3→4→5→6 右链。 因为：时间 O(n) · 空间 O(1)。O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 解法一 非递归
func flatten(root *TreeNode) {
	list := preorder(root)
	for i := 1; i < len(list); i++ {
		prev, cur := list[i-1], list[i]
		prev.Left, prev.Right = nil, cur
	}
	return
}

func preorder(root *TreeNode) (ans []*TreeNode) {
	if root != nil {
		ans = append(ans, root)
		ans = append(ans, preorder(root.Left)...)
		ans = append(ans, preorder(root.Right)...)
	}
	return
}

// 解法二 递归
func flatten1(root *TreeNode) {
	if root == nil || (root.Left == nil && root.Right == nil) {
		return
	}
	flatten(root.Left)
	flatten(root.Right)
	currRight := root.Right
	root.Right = root.Left
	root.Left = nil
	for root.Right != nil {
		root = root.Right
	}
	root.Right = currRight
}

// 解法三 递归
func flatten2(root *TreeNode) {
	if root == nil {
		return
	}
	flatten(root.Right)
	if root.Left == nil {
		return
	}
	flatten(root.Left)
	p := root.Left
	for p.Right != nil {
		p = p.Right
	}
	p.Right = root.Right
	root.Right = root.Left
	root.Left = nil
}

func main() {
    // 1. 主例
    //    输入：mode="preorder", values=[1,2,5,3,4,null,6]
    //    期望：1→2→3→4→5→6 右链。
    //
    // 2. 失败 / 未命中
    //    检查：反序递归 prev 法空间 O(h) 不能与 O(1) 主解混讲;必须先存 oldRight 再改 cur.Right。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC206 反转链表；LC297 序列化
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意标准样例原地展开为前序右链 1→2→3→4→5→6，所有 Left 为 nil。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化O(1) 原地接线:cur 遍历,有左子则找 pre=左子树最右,oldRight=cur.Right,pre.Right=oldRight,cur.Right=cur.Left,cur.Left=nil。
4. 4证明不是新建链表,原地改指针;已处理前缀形成正确前序右链;最终所有 Left=nil。
5. 5复杂度时间 O(n)，空间 O(1)