将N叉树编码为二叉树

这道题让我们将一棵 N 叉树编码为二叉树，其实还需要将二叉树解码回 N 叉树。题目中说了具体的编解码的方法无所谓，那么就怎么简单怎么来呗。首先想一下这道题的难点是什么，N 叉树的特点的每个结点最多有 N 个子结点，而二叉树的每个结点最多只能有两个子结点，那么多余的子结点怎么办，当然只能继续子结点下继续累加，就像泡泡龙游戏一样，一个挂一个的。如何累，得确定一套具体的规则，这样解码的时候，反向来一遍就可以了。对于当前结点 root 的 N 个子结点的处理办法是，将第一个结点挂到二叉树的左子结点上，然后将后面的结点依次挂到右子结点，和右子结点的右子结点上，这样做的好处是，同一层的子结点都挂在右子结点上，而这些子结点自己的子结点都会挂在左子结点上

class Codec {

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