前言

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

正文

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

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

思路分析

這道題類(lèi)似于多叉樹(shù)的序列化和反序列化，不同的是把多叉樹(shù)序列化成二叉樹(shù)，反序列化是從二叉樹(shù)還原成多叉樹(shù)。

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

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

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

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

以下圖為例，節(jié)點(diǎn)a有3個(gè)子節(jié)點(diǎn)，在轉(zhuǎn)化二叉樹(shù)后，節(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)二叉樹(shù)的逆序。判斷二叉樹(shù)的節(jié)點(diǎn)，如果節(jié)點(diǎn)沒(méi)有左孩子那么這個(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)都為多叉樹(shù)的同級(jí)子節(jié)點(diǎn)。

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

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

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

// 多叉樹(shù)節(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;
   }
}
// 二叉樹(shù)節(jié)點(diǎn)定義
public class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) {
      val = x;
   }
}

先看下二叉樹(shù)轉(zhuǎn)二叉樹(shù)的代碼實(shí)現(xiàn)，該方式接收一個(gè)多叉樹(shù)的頭節(jié)點(diǎn)，返回一個(gè)二叉樹(shù)的頭節(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ù)還原為多叉樹(shù)的代碼實(shí)現(xiàn)，同樣是接收一個(gè)二叉樹(shù)的頭節(jié)點(diǎn)，返回多叉樹(shù)的頭結(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;
}

總結(jié)

本文主要介紹如何把一個(gè)多叉樹(shù)轉(zhuǎn)換成二叉樹(shù)以及把二叉樹(shù)還原成多叉樹(shù)，文中分析了多叉樹(shù)和二叉樹(shù)相互轉(zhuǎn)化的過(guò)程，實(shí)現(xiàn)起來(lái)不是很難，但是需要一點(diǎn)技巧，在代碼實(shí)現(xiàn)的過(guò)程中，使用了深度優(yōu)先遍歷。

到此這篇關(guān)于Java實(shí)現(xiàn)多叉樹(shù)和二叉樹(shù)之間的互轉(zhuǎn)的文章就介紹到這了,更多相關(guān)Java 多叉樹(shù)和二叉樹(shù)互轉(zhuǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論