Java实现多叉树和二叉树之间的互转

本文主要介绍了Java实现多叉树和二叉树之间的互转，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧

前言

本文主要介绍如何把一个多叉树转换成二叉树以及把二叉树还原成多叉树。

正文

给出一个多叉树，实现一个函数，这个函数可以把多叉树转成二叉树，再实现一个函数把二叉树还原成多叉树。

如下图所示，将多叉树按某种规则进行转化，转成二叉树，并且能从二叉树再按某种规则还原回来。

思路分析

这道题类似于多叉树的序列化和反序列化，不同的是把多叉树序列化成二叉树，反序列化是从二叉树还原成多叉树。

本题是力扣上的一道付费题目，虽然标记的是困难型的题目，但是说难的话也不是很难，下面来看下具体思路。

本道题只是说按某种规则，并没有明确指明使用什么规则，所以我们制定一个规则就好了。

转成二叉树规则，可以制定如下规则：

将多叉树中任意一个节点x的所有子节点，转为节点x的左子树的右边界。

以下图为例，节点a有3个子节点，在转化二叉树后，节点a只有一个左孩子b，而b有一个有孩子c，c有一个右孩子d。

同样的节点b的子节点e、f转化之后，节点e为节点b的左孩子，节点f为节点e的右孩子。

转化结果为下图所示。

如何还原呢？还原就是转二叉树的逆序。判断二叉树的节点，如果节点没有左孩子那么这个节点一定是叶子节点，例如节点c、节点e、节点f、节点g、节点h、节点i都叶子节点。如果一个节点有左孩子，那么这个左孩子的所有子节点，也就所有右节点都为多叉树的同级子节点。

本次分析的是将多叉树的子节点，转为二叉树的右边界，这个不是固定的，也可以是左边界、也可以是其他形式，只要能转化就可以，这里使用有边界只是举了个例子以及实现方便。

代码实现

根据上面的思路分析，来看下代码实现，首先定义一下多叉树和二叉树的节点定义，多叉树有多个子节点，多以多叉树的子节点使用集合形式表示。

// 多叉树节点定义 public class Node { public int val; // 子节点是列表形式 public List children; public Node(int _val) { val = _val; } public Node(int _val, List _children) { val = _val; children = _children; } } // 二叉树节点定义 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

先看下二叉树转二叉树的代码实现，该方式接收一个多叉树的头节点，返回一个二叉树的头节点：

public TreeNode encode(Node root) { if (root == null) { return null; } TreeNode head = new TreeNode(root.val); head.left = en(root.children); return head; } private TreeNode en(List children) { TreeNode head = null; TreeNode cur = null; for (Node child : children) { TreeNode tNode = new TreeNode(child.val); if (head == null) { head = tNode; } else { cur.right = tNode; } cur = tNode; cur.left = en(child.children); } return head; }

再看下从二叉树还原为多叉树的代码实现，同样是接收一个二叉树的头节点，返回多叉树的头结点：

public Node decode(TreeNode root) { if (root == null) { return null; } return new Node(root.val, de(root.left)); } public List de(TreeNode root) { List children = new ArrayList<>(); while (root != null) { Node cur = new Node(root.val, de(root.left)); children.add(cur); root = root.right; } return children; }