Java实现多叉树和二叉树之间的互转

目录

• 前言
• 正文
• 思路分析
• 代码实现
• 总结

前言

本文主要介绍如何把一个多叉树转换成二叉树以及把二叉树还原成多叉树。

正文

给出一个多叉树，实现一个函数，这个函数可以把多叉树转成二叉树，再实现一个函数把二叉树还原成多叉树。

如下图所示，将多叉树按某种规则进行转化，转成二叉树，并且能从二叉树再按某种规则还原回来。

先看下二叉树转二叉树的代码实现，该方式接收一个多叉树的头节点，返回一个二叉树的头节点：

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

总结

本文主要介绍如何把一个多叉树转换成二叉树以及把二叉树还原成多叉树，文中分析了多叉树和二叉树相互转化的过程，实现起来不是很难，但是需要一点技巧，在代码实现的过程中，使用了深度优先遍历。