Java实现多叉树和二叉树之间的互转_开发_开发者

前言

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

正文

给出一个多叉树，实现一个函数，http://www.devze.com这个函数可以把多叉树转成二叉树，再实现一个函数把二叉树还原成多叉树。

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

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

思路分析

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

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

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

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

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

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

同样的节点b的子节点e、f转化之后，节点e为节点b的左孩子，节点f为http://www.devze.com节点e的右孩子。

转化结果为下图所示。

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

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

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

代码实现

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

// 多叉树节点定义
public class Node {
   public int val;
   // 子节点是列表形式
   public List<Node> children;
   public Node(int _val) {
      val = _val;
   }
   public Node(int _val, List<Node> _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) {
      reandroidturn null;
   }
   TreeNode head = new TreeNode(root.vaandroidl);
   head.left = en(root.children);
   return head;
}
private TreeNode en(List<Node> 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<Node> de(TreeNode root) {
   List<Node> children = new ArrayList<>();
   while (root != null) {
      Node cur = new Node(root.val, de(root.left));
      children.add(cur);
      root = root.right;
   }
   return children;
}