京公网安备11010502063487号给定一棵二叉树，原地把它拉直成一条只用 right 指针连接的链表，顺序是先序遍历的顺序，且每个结点的 left 都要变成空。一个容易漏掉的陷阱是：先用先序遍历收集所有结点到数组，再重新用 right 指针串起来，但忘了把每个结点原来的 left 指针清空——right 链的值序列看起来完全正确，但树的形状并没有真正拉直，仍然残留着旧的 left 分支。本文用真实反例和 5000 组随机树验证，只要原树有左孩子，这个错误就 100% 会发生，再给出正确的原地递归写法、5 种语言实现，以及自底向上拼接的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵二叉树，原地把它"拉直"成一条只用 right 指针连接的链表，顺序是先序遍历的顺序，并且每个结点的 left 都要变成空。一共 5 组用例，覆盖：官方示例、空树、单结点、两结点、只有右孩子的两结点树：
[1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
一个直觉上很自然的写法：先做一次先序遍历，把所有结点按顺序收集到一个数组里，再遍历这个数组，把每个结点的 right 指向下一个结点。这样做出来的 right 链，顺着走确实能读出正确的先序遍历值序列——但很容易漏掉一步：每个结点原来的 left 指针并没有被清空，仍然指向原来的左孩子。right 链看起来是对的，可树的形状其实并没有真正"拉直"：
输入 [1,2,5,3,4,null,6]\n陷阱写法（收集数组后只重连 right，不清空 left） → right链=[1, 2, 3, 4, 5, 6] 残留left指针=true\n正确写法（额外清空每个结点的 left） → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false
两种写法读出来的 right 链完全一样，光看这一串数字很容易误以为陷阱写法也是对的。但题目要求的是"拉直成一条链"，链上的每个结点不应该再有 left 分支——官方的正确性检查会同时验证这两件事。做了一次随机测试，统计"原本就含有左孩子"的随机树里，陷阱写法残留非空 left 指针的比例：
5,000 组随机树中，3,968 组原本就含有左孩子边；\n这些树里陷阱写法残留非空 left 指针的有 3,968 组，占 100.0%
只要原树里存在任何一条"左孩子"边，陷阱写法就一定会留下没清空的 left 指针——这不是偶发的边界情况，而是这种写法本身遗漏了一步操作，系统性地发生。
原地递归，不借助额外数组：helper(node) 把以 node 为根的子树拉直，返回拉直后链的尾结点。先递归拉直左子树、再递归拉直右子树；如果左子树不为空，就把"左链的尾巴"接到原来的右子树上，再把整个左子树平移到 right 位置，最后把 left 清空。时间 O(n)，空间 O(h)（递归栈，不需要额外数组）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def flatten(root): def helper(node): # 原地把 node 为根的子树拉直成一条只用 right 指针的链，返回链尾 if node is None: return None if node.left is None and node.right is None: return node left_tail = helper(node.left) right_tail = helper(node.right) if left_tail: left_tail.right = node.right # 左链的尾巴接上原来的右子树 node.right = node.left # 左子树整体搬到 right 位置 node.left = None # 必须清空，否则不是真正的"链" return right_tail or left_tail helper(root)
$ python3 solution.py [1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
Java · 解法代码class Solution { public void flatten(TreeNode root) { helper(root); } private TreeNode helper(TreeNode node) { if (node == null) return null; if (node.left == null && node.right == null) return node; TreeNode leftTail = helper(node.left); TreeNode rightTail = helper(node.right); if (leftTail != null) { leftTail.right = node.right; // 左链的尾巴接上原来的右子树 node.right = node.left; // 左子树整体搬到 right 位置 node.left = null; // 必须清空，否则不是真正的"链" } return rightTail != null ? rightTail : leftTail; } }
$ javac -d build Main.java && java -cp build Main [1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
Go · 解法代码func flatten(root *TreeNode) { var helper func(node *TreeNode) *TreeNode helper = func(node *TreeNode) *TreeNode { if node == nil { return nil } if node.Left == nil && node.Right == nil { return node } leftTail := helper(node.Left) rightTail := helper(node.Right) if leftTail != nil { leftTail.Right = node.Right // 左链的尾巴接上原来的右子树 node.Right = node.Left // 左子树整体搬到 right 位置 node.Left = nil // 必须清空，否则不是真正的"链" } if rightTail != nil { return rightTail } return leftTail } helper(root) }
$ go run solution.go [1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
JavaScript · 解法代码function flatten(root) { function helper(node) { if (node === null) return null; if (node.left === null && node.right === null) return node; const leftTail = helper(node.left); const rightTail = helper(node.right); if (leftTail) { leftTail.right = node.right; // 左链的尾巴接上原来的右子树 node.right = node.left; // 左子树整体搬到 right 位置 node.left = null; // 必须清空，否则不是真正的"链" } return rightTail || leftTail; } helper(root); }
$ node run.js [1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
C++ · 解法代码class Solution { public: void flatten(TreeNode* root) { helper(root); } private: TreeNode* helper(TreeNode* node) { if (!node) return nullptr; if (!node->left && !node->right) return node; TreeNode* leftTail = helper(node->left); TreeNode* rightTail = helper(node->right); if (leftTail) { leftTail->right = node->right; // 左链的尾巴接上原来的右子树 node->right = node->left; // 左子树整体搬到 right 位置 node->left = nullptr; // 必须清空，否则不是真正的"链" } return rightTail ? rightTail : leftTail; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [1,2,5,3,4,null,6] → right链=[1, 2, 3, 4, 5, 6] 残留left指针=false [] → right链=[] 残留left指针=false [0] → right链=[0] 残留left指针=false [1,2] → right链=[1, 2] 残留left指针=false [1,null,2] → right链=[1, 2] 残留left指针=false
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的原地递归实现另外和"先用数组收集、再重连并清空 left"的写法做了随机对拍，两者都同时检查 right 链的值序列和是否还有残留的 left 指针：
随机对拍 5,000 组（结点数 0 到 12 的随机二叉树），原地递归版与数组重建版（都清空 left）的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [1,2,5,3,4,null,6]：从叶子开始自底向上回溯，每处理完一个结点就把它的左子树（已经拉直成链）接到 right 位置、把左子树的链尾接到原来的右子树上，同时清空 left。蓝色是正在处理的结点，绿色是已经接入最终链的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。