序列化二叉树

public class Solution {
    String Serialize(TreeNode root) {
        // 每个结点以"!"分隔开，方便后续的反序列化
        if (root == null) {
            return "#!";
        }
        // 先序遍历完成序列化
        return root.val + "!" 
            + Serialize(root.left) 
            + Serialize(root.right);
   }
    TreeNode Deserialize(String str) {
       if (str == null || str.length() == 0|| str.equals("#!")) {
           return null;
       }       
        // 使用双端队列来模拟栈stack
        Deque<String>stack = new LinkedList<>();
        // 将所有的结点放入栈，此为先序遍历的结点
        stack.addAll(Arrays.asList(str.split("!")));
        // 先序遍历的方式反序列化
        return Deserialize(stack);
    }
    TreeNode Deserialize(Deque<String>stack) {
        // 栈为空，返回空结点null
        if (stack.isEmpty()) {
            return null;
        }
        String value = stack.pollFirst();
        // 若为空结点，则返回null
        if (value.equals("#")) {
            return null;
        }
        // 先序遍历建树
        TreeNode root = new TreeNode(Integer.parseInt(value));
        root.left = Deserialize(stack);
        root.right = Deserialize(stack);
        return root;
    }
}