Java實現(xiàn)多叉樹和二叉樹之間的互轉

更新時間：2023年05月08日 09:52:50 作者：Java星辰

本文主要介紹了Java實現(xiàn)多叉樹和二叉樹之間的互轉，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

前言

本文主要介紹如何把一個多叉樹轉換成二叉樹以及把二叉樹還原成多叉樹。

正文

給出一個多叉樹，實現(xiàn)一個函數(shù)，這個函數(shù)可以把多叉樹轉成二叉樹，再實現(xiàn)一個函數(shù)把二叉樹還原成多叉樹。

如下圖所示，將多叉樹按某種規(guī)則進行轉化，轉成二叉樹，并且能從二叉樹再按某種規(guī)則還原回來。

思路分析

這道題類似于多叉樹的序列化和反序列化，不同的是把多叉樹序列化成二叉樹，反序列化是從二叉樹還原成多叉樹。

本題是力扣上的一道付費題目，雖然標記的是困難型的題目，但是說難的話也不是很難，下面來看下具體思路。

本道題只是說按某種規(guī)則，并沒有明確指明使用什么規(guī)則，所以我們制定一個規(guī)則就好了。

轉成二叉樹規(guī)則，可以制定如下規(guī)則：

將多叉樹中任意一個節(jié)點x的所有子節(jié)點，轉為節(jié)點x的左子樹的右邊界。

以下圖為例，節(jié)點a有3個子節(jié)點，在轉化二叉樹后，節(jié)點a只有一個左孩子b，而b有一個有孩子c，c有一個右孩子d。

同樣的節(jié)點b的子節(jié)點e、f轉化之后，節(jié)點e為節(jié)點b的左孩子，節(jié)點f為節(jié)點e的右孩子。

轉化結果為下圖所示。

如何還原呢？還原就是轉二叉樹的逆序。判斷二叉樹的節(jié)點，如果節(jié)點沒有左孩子那么這個節(jié)點一定是葉子節(jié)點，例如節(jié)點c、節(jié)點e、節(jié)點f、節(jié)點g、節(jié)點h、節(jié)點i都葉子節(jié)點。如果一個節(jié)點有左孩子，那么這個左孩子的所有子節(jié)點，也就所有右節(jié)點都為多叉樹的同級子節(jié)點。

本次分析的是將多叉樹的子節(jié)點，轉為二叉樹的右邊界，這個不是固定的，也可以是左邊界、也可以是其他形式，只要能轉化就可以，這里使用有邊界只是舉了個例子以及實現(xiàn)方便。

代碼實現(xiàn)

根據(jù)上面的思路分析，來看下代碼實現(xiàn)，首先定義一下多叉樹和二叉樹的節(jié)點定義，多叉樹有多個子節(jié)點，多以多叉樹的子節(jié)點使用集合形式表示。

// 多叉樹節(jié)點定義
public class Node {
   public int val;
   // 子節(jié)點是列表形式
   public List<Node> children;
   public Node(int _val) {
      val = _val;
   }
   public Node(int _val, List<Node> _children) {
      val = _val;
      children = _children;
   }
}
// 二叉樹節(jié)點定義
public class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) {
      val = x;
   }
}

先看下二叉樹轉二叉樹的代碼實現(xiàn)，該方式接收一個多叉樹的頭節(jié)點，返回一個二叉樹的頭節(jié)點：

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<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;
}

再看下從二叉樹還原為多叉樹的代碼實現(xiàn)，同樣是接收一個二叉樹的頭節(jié)點，返回多叉樹的頭結點：

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;
}