快捷導(dǎo)航

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

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

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

前言

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

正文

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

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

思路分析

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

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

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

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

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

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

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

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

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

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

代碼實(shí)現(xiàn)

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

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

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

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

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

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