当前位置:首页 > 技术 > 正文内容

将 N 叉树编码为二叉树

Lotus2022-10-06 20:42技术

将 N 叉树编码为二叉树

作者:Grey

原文地址:

博客园:将 N 叉树编码为二叉树

CSDN:将 N 叉树编码为二叉树

题目描述

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

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

一棵 N 叉树的示例如下

image

二叉树的数据结构如下

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 叉树中每个节点的子节点转换成自己左树的右边界或者右树的左边界,示例图如下

image

二叉树编码成 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叉树的互相转换

更多

算法和数据结构笔记

扫描二维码推送至手机访问。

版权声明:本文来源于网络,仅供学习,如侵权请联系站长删除。

本文链接:https://news.layui.org.cn/post/284.html

分享给朋友:

“将 N 叉树编码为二叉树” 的相关文章

HBase1.4.6安装搭建及shell命令使用

HBase1.4.6安装搭建 目录 HBase1.4.6安装搭建 一、前期准备(Hadoop,zookeeper,jdk) 搭建Hbase 1、上传解压 2、配置环境变量 3、修改hbase-env.sh文件 4、修改hbase-site.xml文件 5、修改regionservers文件 6、同步到所有节点(如果是伪分布式不需要同步) 7、启动hbase集群 , 在master上执行...

第三章 知己知彼

知彼知己,百战不殆;不知彼而知己,一胜一负;不知彼,不知己,每战必殆。《谋攻篇》 前面两章其实重点是在掰扯数智化,IT研发本身的数字化其实除了DevOps这一种手段之外还有很多,比如Low Code、RPA等等,AI都可以自动写代码了,还有啥是不可能的呢!不过本人能力有限,这点斤两也就敢玩玩DevOps,其他的碰都就不敢碰,接下来聚焦到DevOps的一些见解上。 3.1 剑锋所指      ...

记Windows的一个存在了十多年的bug

bug Windows有一个bug,持续了十多年,从Windows Visita开始(2007年),一直存在,直到Windows11(2021年)才修复(其实也不叫修复,后面我再具体说),而Windows10还能重现这个bug,即便把系统更新到最新(2022年10月5日)。 这个bug用语言来描述就是:使用Windows Explorer(资源管理器)的树形结构初次展开目录时,滚动条会发生不正确...

源码学习之MyBatis的底层查询原理

导读 本文通过MyBatis一个低版本的bug(3.4.5之前的版本)入手,分析MyBatis的一次完整的查询流程,从配置文件的解析到一个查询的完整执行过程详细解读MyBatis的一次查询流程,通过本文可以详细了解MyBatis的一次查询过程。在平时的代码编写中,发现了MyBatis一个低版本的bug(3.4.5之前的版本),由于现在很多工程中的版本都是低于3.4.5的,因此在这里用一个简单的例...

国庆节,零代码帮你搞定假期美食菜单

当国庆假期遇上美食 每一口都唇齿留香 特色美食太多,不知道吃什么? AppCube带你一分钟搞定假期美食 来一场舌尖上的旅行 零代码,让假期生活有滋有味 国庆小长假,三五好友结伴出游,最纠结的莫过于中午吃什么,晚上吃什么?翻翻攻略,当地特色美食令人眼花缭乱……体验通过AppCube设计一款“国庆假期美食菜单收集”应用,解决大家的选择困难症。 基于AppCube零代码能力,小白也能DIY应用开发...

Docker入门学习

1.运行第一个docker容器 docker run -i -t ubuntu /bin/bash 参数说明: -i, --interactive=false, 打开STDIN,用于控制台交互-t, --tty=false, 分配tty设备,该可以支持终端登录,默认为false-d, --detach=false, 指定容器运行于前台还是后台,默认为false 首先,docker run -it...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。