leetcode 431. 将 N 叉树编码为二叉树

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 一、解题思路
• 二、代码
• • 1.多叉树转二叉树
  • 2.二叉树转多叉树

431. 将 N 叉树编码为二叉树

设计一个算法，可以将 N 叉树编码为二叉树，并能将该二叉树解码为原 N 叉树。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。类似地，一个二叉树是指每个节点都有不超过 2 个孩子节点的有根树。你的编码 / 解码的算法的实现没有限制，你只需要保证一个 N 叉树可以编码为二叉树且该二叉树可以解码回原始 N 叉树即可。

1.多叉树转换为二叉树
多叉树的头结点为二叉树的头结点,多叉树的孩子依次放在二叉树的左树右节点上

2.二叉树转换为多叉树
二叉树的头结点为多叉树的头结点,二叉树的右树左孩子依次为多叉树的孩子

代码如下（示例）：

	public TreeNode encode(Node root) {
        if(root==null){
            return null;
        }
        TreeNode head=new TreeNode(root.val);
        head.left=en(root.children);
        return head;
	}
	public TreeNode en(List children){
        TreeNode head=null;
        TreeNode cur=null;
        for(Node child:children){
            TreeNode node=new TreeNode(child.val);
            if(head==null){
                head=node;
            }else{
                cur.right=node;
            }
            cur=node;
            cur.left=en(child.children);
        }
        return head;
	}

代码如下（示例）：

	public Node decode(TreeNode root) {
        if(root==null){
            return null;
        }
        Node head=new Node(root.val,de(root.left));
        return head;
    }
    public List de(TreeNode root){
        List ans=new ArrayList<>();
        while(root!=null){
            Node node=new Node(root.val,de(root.left));
            ans.add(node);
            root=root.right;
        }
        return ans;
    }