[LintCode] Binary Tree Serialization [看不到命运 只看到紫薇]

java 5 2016-02-29 13:03
女装

Problem

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

There is no limit of how you deserialize or serialize a binary tree, you only need to make sure you can serialize a binary tree to a string and deserialize this string to the original structure.

Example

An example of testdata: Binary tree {3,9,20,#,#,15,7} denote the following structure:

  3
 / \
9  20
  /  \
 15   7

Our data serialization use bfs traversal. This is just for when you got wrong answer and want to debug the input.
You can use other method to do serializaiton and deserialization.

Note

String[] vals = data.substring(1, data.length() - 1).split(",");  

这里要注意的是split()的用法。所以记住,用split()可以从String自动分离出数组。

.substring(beginIndex, endIndex) 

beginIndex(Inclusive), endIndex(exclusive). So, the '{' and '}' are not included in vals[].

Solution

class Solution {

    public String serialize(TreeNode root) {
        if (root == null) {
            return "{}";
        }
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(root);
        for (int i = 0; i < queue.size(); i++) {
            TreeNode node = queue.get(i);
            if (node == null) {
                continue;
            }
            queue.add(node.left);
            queue.add(node.right);
        }
        
        //Of course we can delete this.
        /*
        while (queue.get(queue.size() - 1) == null) {
            queue.remove(queue.size() - 1);
        }
        */
        
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        sb.append(queue.get(0).val);//remember to add .val
        for (int i = 1; i < queue.size(); i++) {
            if (queue.get(i) == null) {
                sb.append(",#");
            } else {
                sb.append(",");
                sb.append(queue.get(i).val);
            }
        }
        sb.append("}");
        return sb.toString(); //sb is not String, we have to transform
    }

    public TreeNode deserialize(String data) { //more tricky!
        if (data.equals("{}")) {
            return null;
        }
        
        //跳过data第一个元素并放入String数组最快捷语句
        String[] vals = data.substring(1, data.length() - 1).split(",");
        
        //建立ArrayList的用意:记录处理过的结点
        //并按index处理所有结点:和自己的children连接
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.add(root);
        int index = 0;
        boolean isLeftChild = true;
        for (int i = 1; i < vals.length; i++) {
            if (!vals[i].equals("#")) {
                //vals[i] is a String, so use parseInt()
                TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
                if (isLeftChild) {
                    queue.get(index).left = node;
                } else {
                    queue.get(index).right = node;
                }
                queue.add(node);
            }
            
            //下面先通过isLeftChild判断index,
            //再修改isLeftChild的符号的顺序,十分巧妙
            if (!isLeftChild) {
                index++;
            }
            isLeftChild = !isLeftChild;
        }
        return root;
    }
}
女装
文章评论