目錄

• 前言
• 正文
• 思路分析
• 代碼實現
• 總結

前言

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

正文

給出一個多叉樹，實現一個函數，這個函數可以把多叉樹轉成二叉樹，再實現一個函數把二叉樹還原成多叉樹。

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

先看下二叉樹轉二叉樹的代碼實現，該方式接收一個多叉樹的頭節點，返回一個二叉樹的頭節點：

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

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

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

總結

本文主要介紹如何把一個多叉樹轉換成二叉樹以及把二叉樹還原成多叉樹，文中分析了多叉樹和二叉樹相互轉化的過程，實現起來不是很難，但是需要一點技巧，在代碼實現的過程中，使用了深度優先遍歷。