LeetCode 431. 将 N 叉树编码为二叉树

2020-04-15 HGNULB 约 6 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 431. 将 N 叉树编码为二叉树

题意分析

题目目标：设计一对互逆的函数，encode 把一棵每个节点可以有任意多个孩子的树转成一棵二叉树，decode 再从这棵二叉树完整还原出原来的树，要求还原结果与原树结构和取值完全一致。
核心约束：题目不检查中间那棵二叉树长什么样，只检查往返之后是否与原树相同，这说明我们有充分的自由去设计编码方案，唯一的硬要求是这个映射必须是单射——不同的 N 叉树不能编成同一棵二叉树，否则无法还原。第二个信号是「N 叉」与「二叉」的差距只在于孩子的数量不固定，而二叉树每个节点恰好有两个指针位可用，所以问题的实质是：用两个固定指针位去表达一个不定长的孩子列表。第三个信号是子节点的顺序有意义，还原时必须保持原来的先后次序。
边界处理：根可能为空，两个方向都要直接返回空；节点可能没有孩子，此时不能对空引用继续挂载兄弟；节点值的取值范围题目不做特殊限制，因此不能用哨兵值来表示结构信息；树可能很深也可能很宽，递归实现要意识到栈深度取决于树的形态。

解法：左孩子右兄弟编码

核心思路

二叉节点只有两个指针，但 N 叉节点的孩子数量不定。左孩子右兄弟表示法为两个指针规定固定语义：

left 指向当前节点的第一个孩子；

从该孩子开始，连续的 right 指针依次连接它的兄弟。

这样，一个有序孩子列表被编码成“左指针进入、右指针遍历”的单链表。编码时依次递归创建孩子并串起右链；解码时从 left 出发沿右链遍历，按原顺序递归还原每个孩子。

编码不变量：encode(node) 返回的二叉节点完整表示 node 的 N 叉子树；其 left 链首与后续 right 链按顺序对应所有直接孩子，而返回节点自己的 right 留给调用者连接兄弟。

正确性：对叶子节点，两种表示都没有孩子。假设孩子子树都能正确往返，编码会按原顺序把它们串成兄弟链，解码又按同一顺序逐个取回并递归还原。因此由树高归纳，所有节点的值、父子关系和孩子顺序都保持不变，decode(encode(root)) 与原树相同。

解题步骤

空节点在编码和解码时都返回空。

编码当前值；将第一个编码后的孩子挂到 left，其余孩子依次挂到前一个孩子的 right。

解码当前值并创建空孩子列表；从二叉节点的 left 开始沿 right 链，逐个递归解码并追加。

若节点 1 的孩子依次为 [3,2,4]，编码后 1.left = 3、3.right = 2、2.right = 4。解码沿这条右链读取，仍得到 [3,2,4]，不会改变顺序。

空树、叶子节点、只有一个孩子以及很宽的孩子列表都使用同一约定；节点值不承担任何结构含义。

代码实现

import java.util.ArrayList;

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)$，每个节点和每条孩子关系只处理一次。

空间复杂度：除输出外为 $O(h)$，其中 h 是 N 叉树高度，来自递归调用栈。

关键点总结

left 只表示第一个孩子，right 只表示下一个兄弟；指针语义不能混用。

孩子顺序通过兄弟右链保存，编码和解码必须按相同方向遍历。

当前节点自己的 right 由父层负责连接，递归函数只构造当前子树的孩子链。

编解码互逆可用树高归纳证明，无需使用哨兵值或额外元数据。

易错点总结

把第二个孩子挂到当前节点的 right：会把“孩子”和“兄弟”两种语义混在同一指针上。

兄弟链追加后不移动游标：后续孩子会覆盖前一个孩子，只留下链首和最后一个。

解码从 root 而不是 root.left 开始：会把节点自身当作自己的孩子。

倒序连接兄弟：解码后的孩子顺序会反转。

叶子节点使用空指针孩子列表：Java 解码时应初始化空列表，保证可以安全追加孩子。

相似题目

题目	难度	考察点
428. 序列化和反序列化 N 叉树	困难	目标是线性字符串而非树，需要自己设计孩子数量的记录方式与分隔符
297. 二叉树的序列化与反序列化	困难	二叉树转字符串，重点是用空占位符保留结构信息以便无歧义还原
449. 序列化和反序列化二叉搜索树	中等	可利用有序性省去空占位符，考察如何借助额外性质压缩编码长度
589. N 叉树的前序遍历	简单	N 叉树遍历的基本功，练习按顺序枚举孩子列表的递归与迭代写法
429. N 叉树的层序遍历	中等	换成广度优先视角，考察队列中如何一次性展开不定数量的孩子
606. 根据二叉树创建字符串	中等	同为可逆表示设计，难点在于何时可以省略空括号而不破坏唯一性