LC431. Encode N-ary T to BT

Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
(src: stateless)

---

encode的问题，怎么简单怎么来

1. N-ary: level: 都是left child的right child

N-ary Tree:

	      1
	   /  |  \
	  3   2   4
	 / \
	5   6


Binary Tree:

		    1
		   /
		  3
		 / \
		5   2
		 \   \
		  6   4

1. Node类型的root: 作为N-ary, left child来自于children这个list的第一个元素
2. TreeNode类型的cur每次选right child进行递归; 只可能是BT类型的节点的right child递归

   /*
   // Definition for a Node.
   class Node {
       public int val;
       public List<Node> children;
   
       public Node() {}
   
       public Node(int _val) {
           val = _val;
       }
   
       public Node(int _val, List<Node> _children) {
           val = _val;
           children = _children;
       }
   };
   */
   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Codec {
   
       // Encodes an n-ary tree to a binary tree.
       public TreeNode encode(Node root) {
           if (root == null) return null;
           
           TreeNode res = new TreeNode(root.val);
           if (root.children.size() > 0) {
               res.left = encode(root.children.get(0));
           }
           TreeNode cur = res.left;
           for (int i = 1; i < root.children.size(); ++i) {
               cur.right = encode(root.children.get(i));
               cur = cur.right;
           }
           return res;
       }
   
       // Decodes your binary tree to an n-ary tree.
       public Node decode(TreeNode root) {
           if (root == null) return null;
           Node res = new Node(root.val, new LinkedList<>());
           TreeNode cur = root.left;
           while (cur != null) {
               res.children.add(decode(cur));
               cur = cur.right;
           }
           return res;
       }
   }
   
   // Your Codec object will be instantiated and called as such:
   // Codec codec = new Codec();
   // codec.decode(codec.encode(root));