先序遍历递归实现序列化与反序列化

1.采用层次遍历虽然易于人观察，但代码实现起来麻烦，本次借鉴leetcode官方题解，采用先序遍历实现序列化与反序列化。
2.先序遍历的按 root -> left subtree -> right subtree（根左右）的顺序递归进行，例如下面这幅图

注意：按牛客网的格式，结果应为 "1!2!3!#!#!4!#!#!5!#!#!" 即用#表示空节点，且每个节点后跟!表示结束。

    /**
     * 先序遍历序列化二叉树
     * @param root
     * @return
     */
    public String Serialize(TreeNode root) {
        return rSerialize(root, "");
    }

    private String rSerialize(TreeNode root, String s) {
        if (root == null)
            s+= "#!";
        else {
            s += root.val+"!";
            s = rSerialize(root.left, s);
            s = rSerialize(root.right,s);
        }
        return s;
    }

3.现在让我们反序列化"1!2!3!#!#!4!#!#!5!#!#!" ，同样采用先序遍历的思想，为了方便观察和后续操作，我们先将其分割成数组并存入链表。[1 , 2, 3, #, #, 4, #, #, 5, #, #]
先序遍历的数组总是可以分为三部分[ [根] , [左子树的先序序列] , [右子树的先序序列] ]，且每部分的首位元素为该部分子树的根节点。
如 [ 1 ] 是 [2, 3, #, #, 4, #, #] [5, #, #] 的父节点。
而[ 2 ]又是[ 3, #, #] [4, #, #]的父节点
以此类推...
按照这种思想，我们写出反序列化的代码：

    /**
     * 反序列化先序，通过字符串构建树
     * @param str
     * @return
     */
    public TreeNode Deserialize(String str) {
        String[] nodes = str.split("!");    //将字符串划分成数组
        List<String> node_list = new LinkedList<>(Arrays.asList(nodes));
        return rDeserialize(node_list);
    }


    private TreeNode rDeserialize(List<String> node_list) {
        //当前节点为空，则返回null
        if (node_list.get(0).equals("#") || node_list.get(0) == "#"){
            node_list.remove(0);
            return null;
        }
        //总是根据首位元素确定当前子树的根
        TreeNode root = new TreeNode(Integer.valueOf(node_list.get(0)));
        node_list.remove(0);    
        root.left = rDeserialize(node_list);    
        root.right = rDeserialize(node_list);
        //返回当前jiedian
        return root;
    }