//https://leetcode.com/problems/serialize-and-deserialize-bst/
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return "#";
        return Integer.toString(root.val) + "," + serialize(root.left) + "," + serialize(root.right);
    }
    class Data{
        TreeNode node;
        int f;
        Data(TreeNode n){
            node = n;
            f = 0;
        }
    }
    TreeNode decode(String[] v) {
        Stack<Data> stk = new Stack();
        for (int i = 0; i < v.length; i++) {
            while (!stk.isEmpty() && stk.peek().f == 2) {
                stk.pop();
            }
            TreeNode node = v[i].equals("#") ? null : new TreeNode(Integer.parseInt(v[i]));
            if (node == null && stk.isEmpty()) return null;
            if (!stk.isEmpty()) {
                Data top = stk.peek();
                if (top.f == 0) {
                    top.node.left = node;
                } else {
                    top.node.right = node;
                }
                top.f++;
            }
            if (node != null) stk.push(new Data(node));
        }
        while (stk.size() >= 2) stk.pop();
        return stk.pop().node;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        System.out.println(data);
        return decode(data.split(","));
    }
}

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