297. 二叉树的序列化与反序列化

package treeAndRecursion.code297;
import treeAndRecursion.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
 *         1
 *       /  \
 *      2    3
 *          / \
 *         4   5
 *
 *  面对这样一棵树，序列化的时候，因为使用先序遍历无法确定树的结构，因为不知道一个分支在哪停止了
 *  所以只需要遍历一个分支的时候，把下面的null也存起来，就可以清楚的知道哪一个分支在哪停止了
 *  所以上面的树的先序遍历可以使用  1,2,null,null,3,4,null,null,5,null,null
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<String> res = new ArrayList<>();
        bfs(root,res);
        return String.join(",",res);
    }
    //先序遍历，遇到空的时候存一下空然后再返回
    //先序： 根 左 右
    public void bfs(TreeNode node, List<String> res){
        if(node == null){
            res.add("null");
            return;
        }
        res.add(String.valueOf(node.val));
        bfs(node.left,res);
        bfs(node.right,res);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        dataArr = data.split(",");
        //从下标0开始走
        cur = 0;
        return restore();
    }
    //定义两个共享变量去辅助还原方法
    //1:当前的序列化结果，用，分割成数组
    private String[] dataArr;
    //2:当前走到了哪一个下标了
    private Integer cur;
    public TreeNode restore(){
        //递归结束条件，如果走到了null，说明当前分支结束了，再走一步，然后返回null
        if(dataArr[cur].equals("null")){
            //只要cur用过了，就要再走一步++
            cur++;
            return null;
        }
        //产生当前这一递归层的根节点
        TreeNode root = new TreeNode(Integer.parseInt(dataArr[cur]));
        //只要cur用过了，就要再走一步++
        cur++;
        //递归复原当前这一层的左右子树
        root.left = restore();
        root.right = restore();
        return root;
    }
}