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

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

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

前言

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

正文

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

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

思路分析

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

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

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

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

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

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

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

轉(zhuǎn)化結(jié)果為下圖所示。

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

本次分析的是將多叉樹的子節(jié)點，轉(zhuǎn)為二叉樹的右邊界，這個不是固定的，也可以是左邊界、也可以是其他形式，只要能轉(zhuǎn)化就可以，這里使用有邊界只是舉了個例子以及實現(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;
   }
}

先看下二叉樹轉(zhuǎn)二叉樹的代碼實現(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é)點，返回多叉樹的頭結(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;
}