Encode N-ary Tree to Binary Tree

实现n-ary tree和binary tree的互相转化.

这个题就是注意观察, 我的方法是:

n-ary to binary: 每个binary的node都是n-ary的node, binary的node的left是n-ary的children, binary的node的right是children的数量.

比如例题:

就变成了

binary to n-ary: 因为已知一个node的右侧是左侧node的数量. 所以直接搜索即可.

/*
// 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 node = new TreeNode(root.val);
        node.right = new TreeNode(root.children.size());
        TreeNode p = node;
        for(int i = 0; i < root.children.size(); i++) {
            p.left = encode(root.children.get(i));
            while(p.left != null){
                p = p.left;
            }
        }
        return node;
    } 
	
    // Decodes your binary tree to an n-ary tree.
    public Node decode(TreeNode root) { 
        if(root == null)
            return null;
        Node node = new Node(root.val, new ArrayList<Node>());
        for(int i = 0; i < root.right.val; i++) {
            Node cur = decode(root.left);
            node.children.add(cur);
            root.left = root.left.left;
        }
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(root));