LeetCode 431. 将 N 叉树编码为二叉树
题目描述
题意分析
将一棵有序 N 叉树转换为二叉树，并能从编码结果还原原来的节点值、父子关系和孩子顺序。N 叉节点可以有任意多个孩子，而二叉节点只有两个指针，需要约定这两个指针如何表达一整个孩子列表。
本文未保留完整原题及节点定义，现有实现约定：N 叉节点的孩子列表按顺序保存实际子节点，不含空占位；Java 叶节点的
children是空列表而非null。二叉节点提供左右指针，解码输入是符合下述编码规则的二叉树，空树以空引用表示。
解法：左孩子右兄弟编码
核心思路
[!blue]
为每个原节点创建一个保存相同值的二叉节点，并固定两种指针含义：
left指向它的第一个孩子，right指向它的下一个兄弟。父节点只需通过left进入孩子列表，其余孩子沿right串成链，就能表达任意数量的孩子。编码当前节点时，按原列表顺序递归编码每个孩子，用
previousChild记录已经接好的最后一个孩子。第一个孩子接到当前节点的left，之后每个孩子接到前一个孩子的right，再移动previousChild。孩子自身的left仍用于它的下一层子节点，因此孩子关系与兄弟关系不会混淆。当前递归只编码“这个节点及其后代”，返回节点的
right留给父层连接兄弟。整棵树的根没有兄弟，右指针为空；叶节点没有孩子，左指针为空。节点值无需承担任何分隔或标记作用，重复值也不影响结构表达。解码时，先恢复当前值，再从
root.left开始沿right遍历孩子链。链上每个节点递归解码后，按遍历顺序追加到当前孩子列表。递归不会把当前节点自己的right作为它的孩子处理，这个兄弟链接由上一层循环消费。对每个节点，编码将有序孩子列表转成唯一的有序右链，解码又按同一条链恢复列表；递归对子树执行相同过程。于是所有节点值、父子关系和孩子顺序都能逐层还原，编码与解码互相对应。
解题步骤
- 编码或解码遇到空节点，直接返回空。
- 编码时创建当前二叉节点，将前驱孩子设为空，按原顺序递归处理孩子并连接左指针或兄弟右指针。
- 解码时创建当前 N 叉节点及空孩子列表，从左指针找到第一个孩子。
- 沿右链逐个递归解码并追加孩子，直到兄弟链结束，返回当前节点。
代码实现
class Codec {
public TreeNode encode(Node root) {
if (root == null) {
return null;
}
TreeNode encodedRoot = new TreeNode(root.val);
TreeNode previousChild = null;
for (Node child : root.children) {
TreeNode encodedChild = encode(child);
// 第一个孩子走左指针，后续孩子连接前一个孩子的右指针。
if (previousChild == null) {
encodedRoot.left = encodedChild;
} else {
previousChild.right = encodedChild;
}
previousChild = encodedChild;
}
return encodedRoot;
}
public Node decode(TreeNode root) {
if (root == null) {
return null;
}
Node decodedRoot = new Node(root.val, new ArrayList<>());
// 从第一个孩子沿兄弟链遍历，递归只恢复每个孩子的子树。
for (TreeNode child = root.left; child != null; child = child.right) {
decodedRoot.children.add(decode(child));
}
return decodedRoot;
}
}
type Codec struct{}
func Constructor() *Codec {
return &Codec{}
}
func (c *Codec) encode(root *Node) *TreeNode {
if root == nil {
return nil
}
encodedRoot := &TreeNode{Val: root.Val}
var previousChild *TreeNode
for _, child := range root.Children {
encodedChild := c.encode(child)
// 第一个孩子走左指针，后续孩子连接前一个孩子的右指针。
if previousChild == nil {
encodedRoot.Left = encodedChild
} else {
previousChild.Right = encodedChild
}
previousChild = encodedChild
}
return encodedRoot
}
func (c *Codec) decode(root *TreeNode) *Node {
if root == nil {
return nil
}
decodedRoot := &Node{Val: root.Val, Children: make([]*Node, 0)}
// 从第一个孩子沿兄弟链遍历，递归只恢复每个孩子的子树。
for child := root.Left; child != nil; child = child.Right {
decodedRoot.Children = append(decodedRoot.Children, c.decode(child))
}
return decodedRoot
}
复杂度分析
- 时间复杂度：编码、解码均为 $O(n)$，其中 $n$ 是节点数。每个节点创建一次，每条孩子关系处理一次。
- 空间复杂度：辅助递归栈为 $O(h)$，其中 $h$ 是原 N 叉树高度。同层兄弟由循环处理，不会因为编码后的右链很长而额外加深递归；新生成的树另占 $O(n)$。
关键点总结
[!green]
- left 与 right 的角色固定，分别是孩子与兄弟。
- 兄弟链由循环处理，递归深入的是孩子子树。
- 结构由指针表达，节点值不承担分隔标记。
易错点总结
[!yellow]
- 将第二个孩子挂到父节点 right：把它编码成父节点的兄弟。
- 追加兄弟后不移动前驱：后续节点会覆盖已有连接。
- 解码从 root 自身开始：把节点当作自己的孩子。
- 倒序连接兄弟：还原后的孩子顺序改变。