将 N 叉树编码为二叉树

作者：Grey

原文地址：

题目描述

将一棵n叉树编码为一棵二叉树，并对二叉树进行解码，得到原始的n叉树。 n叉树是一棵有根树，其中每个节点的子树不超过n个。类似地，二叉树是一棵有根树，其中每个节点的子树不超过2个。编码/解码算法的工作方式不受限制。您只需要确保一个n叉树可以被编码为一个二叉树，并且这个二叉树可以被解码为原始的n叉树结构。

题目链接：LintCode 1530 · Encode N-ary Tree to Binary Tree

一棵 N 叉树的示例如下

将 N 叉树编码为二叉树

二叉树的数据结构如下

class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

N 叉树的数据结构如下

class UndirectedGraphNode {
     int label;
     List<UndirectedGraphNode> neighbors;
     UndirectedGraphNode(int x) {
         label = x;
         neighbors = new ArrayList<UndirectedGraphNode>();
     }
}

每个节点有属于自己的 label 值，也有若干个孩子节点，即List<UndirectedGraphNode> neighbors。

我们需要实现如下两个方法

// N 叉树编码成 二叉树
TreeNode encode(UndirectedGraphNode root)
// 二叉树编码成 N 叉树
UndirectedGraphNode decode(TreeNode root)

主要思路

N 叉树编码成二叉树的方法是将 N 叉树中每个节点的子节点转换成自己左树的右边界或者右树的左边界，示例图如下

将 N 叉树编码为二叉树

二叉树编码成 N 叉树的方法就是把每个节点的左树右边界存到一个 List 里面，作为这个节点的子节点列表即可，就是上述示例图的逆过程。

N 叉树编码成二叉树的过程就是一个深度优先遍历，首先

TreeNode head = new TreeNode(root.label);

表示二叉树的根节点就是 N 叉树的根节点，

然后将根节点的孩子节点，调用递归，进行深度优先遍历，代码如下

// 将某个节点的孩子节点挂在其右树的左边界上
// 将 N 叉树的根节点的孩子节点做深度优先遍历
// 并将其挂在根节点的右树上
head.right = en(root.neighbors);

// 深度优先遍历
private TreeNode en(List<UndirectedGraphNode> neighbors) {
        TreeNode c = null;
        TreeNode head = null;
        for (UndirectedGraphNode neighbor : neighbors) {
            TreeNode node = new TreeNode(neighbor.label);
            if (head == null) {
                // 头节点为空，建出来
                head = node;
            } else {
                // 否则挂在当前节点的右树的左边界上
                c.left = node;
            }
            c = node;
            c.right = en(neighbor.neighbors);
        }
        return head;
}

将二叉树转换成 N 叉树的逻辑如下：

首先

UndirectedGraphNode node = new UndirectedGraphNode(root.val);

表示：N 叉树的根节点也是二叉树的根节点。

接着调用递归，将二叉树的右树构造出 N 叉树当前节点的孩子节点。

// 将二叉树的右树构造出 N 叉树当前节点的孩子节点
node.neighbors = de(root.right);

public ArrayList<UndirectedGraphNode> de(TreeNode root) {
    ArrayList<UndirectedGraphNode> children = new ArrayList<>();
    while (root != null) {
        UndirectedGraphNode cur = new UndirectedGraphNode(root.val);
        cur.neighbors = de(root.right);
        children.add(cur);
        root = root.left;
    }
    return children;
}

其中 while 循环中就是不断的把当前节点的左树右边界加入到一个 List 中，最后返回。

完整代码如下

public class Solution {
    public UndirectedGraphNode decode(TreeNode root) {
        if (root == null) {
            return null;
        }
        UndirectedGraphNode node = new UndirectedGraphNode(root.val);
        node.neighbors = de(root.right);
        return node;
    }

    public ArrayList<UndirectedGraphNode> de(TreeNode root) {
        ArrayList<UndirectedGraphNode> children = new ArrayList<>();
        while (root != null) {
            UndirectedGraphNode cur = new UndirectedGraphNode(root.val);
            cur.neighbors = de(root.right);
            children.add(cur);
            root = root.left;
        }
        return children;
    }

    // 每个子节点转换成自己左树的右边界或者右树的左边界 + 深度优先遍历
    // 编码
    public TreeNode encode(UndirectedGraphNode root) {
        if (root == null) {
            return null;
        }
        TreeNode head = new TreeNode(root.label);
        // 右树的左边界
        head.right = en(root.neighbors);
        return head;
    }

    private TreeNode en(List<UndirectedGraphNode> neighbors) {
        TreeNode c = null;
        TreeNode head = null;
        for (UndirectedGraphNode neighbor : neighbors) {
            TreeNode node = new TreeNode(neighbor.label);
            if (head == null) {
                // 头节点为空，建出来
                head = node;
            } else {
                // 否则挂在当前节点的右树的左边界上
                c.left = node;
            }
            c = node;
            c.right = en(neighbor.neighbors);
        }
        return head;
    }
}

本文涉及到的所有图例见：二叉树与N叉树的互相转换

算法和数据结构笔记

秒客网

将 N 叉树编码为二叉树

题目描述

主要思路

更多

相关文章