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

Categories:

题目描述
思路分析
1. 解法一：左孩子右兄弟编码（推荐）
相似题目

题目描述

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

思路分析

解法一：左孩子右兄弟编码（推荐）

核心思路：

经典的 N 叉树转二叉树方法：左孩子右兄弟表示法

编码规则：将 N 叉树节点的第一个子节点映射为二叉树的左孩子；将该节点的下一个兄弟节点映射为二叉树的右孩子

解码规则：二叉树节点的左孩子是 N 叉节点的第一个子节点；右孩子是该节点的下一个兄弟，依次连接即可还原所有子节点

递归地对每个节点执行上述转换，即可完成整棵树的编解码

复杂度分析：

时间复杂度：O(n)，其中 n 为树的节点总数，每个节点恰好访问一次

空间复杂度：O(n)，递归栈深度最坏为 O(n)（链状树）

class Codec {

    // 编码：N 叉树 -> 二叉树
    public TreeNode encode(Node root) {
        if (root == null) {
            return null;
        }

        TreeNode binaryNode = new TreeNode(root.val);

        if (!root.children.isEmpty()) {
            // 第一个子节点映射为二叉树左孩子
            binaryNode.left = encode(root.children.get(0));
        }

        // 将其余兄弟节点依次挂到右孩子链上
        TreeNode curr = binaryNode.left;
        for (int i = 1; i < root.children.size(); i++) {
            curr.right = encode(root.children.get(i));
            curr = curr.right;
        }

        return binaryNode;
    }

    // 解码：二叉树 -> N 叉树
    public Node decode(TreeNode root) {
        if (root == null) {
            return null;
        }

        Node naryNode = new Node(root.val, new ArrayList<>());

        // 遍历左孩子的右兄弟链，还原所有子节点
        TreeNode curr = root.left;
        while (curr != null) {
            naryNode.children.add(decode(curr));
            curr = curr.right;
        }

        return naryNode;
    }
}

// 编码：N 叉树 -> 二叉树
func (c *Codec) encode(root *Node) *TreeNode {
    if root == nil {
        return nil
    }

    binaryNode := &TreeNode{Val: root.Val}

    if len(root.Children) > 0 {
        // 第一个子节点映射为二叉树左孩子
        binaryNode.Left = c.encode(root.Children[0])
    }

    // 将其余兄弟节点依次挂到右孩子链上
    curr := binaryNode.Left
    for i := 1; i < len(root.Children); i++ {
        curr.Right = c.encode(root.Children[i])
        curr = curr.Right
    }

    return binaryNode
}

// 解码：二叉树 -> N 叉树
func (c *Codec) decode(root *TreeNode) *Node {
    if root == nil {
        return nil
    }

    naryNode := &Node{Val: root.Val}

    // 遍历左孩子的右兄弟链，还原所有子节点
    curr := root.Left
    for curr != nil {
        naryNode.Children = append(naryNode.Children, c.decode(curr))
        curr = curr.Right
    }

    return naryNode
}

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	树的序列化
428. 序列化和反序列化 N 叉树	困难	树的序列化
589. N 叉树的前序遍历	简单	N 叉树遍历
590. N 叉树的后序遍历	简单	N 叉树遍历
114. 二叉树展开为链表	中等	二叉树变换
116. 填充每个节点的下一个右侧节点指针	中等	树的结构变换

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/18641661