Binary Tree Serialization 解题报告

A collection of Hello World applications from helloworld.org.

标签（空格分隔）： lintcode BFS BinaryTree

题目

link点我
Example
An example of testdata: Binary tree {3,9,20,#,#,15,7}, denote the following structure, Our data serialization use bfs traversal:
1
使用code block可以保留格式 3 / \ 9 20 / \ 15 7

分析

Serialize

注意这个是Lintcode的Serialize, 和Leetcode的区别在于他使用的是BFS. 而后者则是使用的pre-order DFS.
null object 和 null的区别.
flag的设计: 要有初始值, 在进入循环的时候update, 对于每一个节点再次update. 那么当这一层结束后就是有效的flag.

De-serialize

还是使用BFS解决. 和Pre-order的de-serialize一样, 和各自的Serialize有一个一一对应的关系.
第一次写的时候出现idx超出array size的问题. 这是为什么呢? 因为我在判断token[idx]的时候居然判断了4次. 因为每一次判断都要idx++. 然后我把4个if并成2个if…else就OK了.
注意这个时候的while loop判断不是parents queue是否为空, 而是判断token[] array走完没有. 我一开始这里搞错了, 居然去判断string走完没有. 注意string就是char Array. 例如{3, 9, 20, #, #, 15, 7}, 这个string的length是21. 而token[]则是7.
还有注意这里update parents queue的时候要注意. 这里的做法是对于”#”, 则不加入null到queue. 不然queue的size()就不对了. 因为这里不用traverse null node.

code

1. Serialize Binary Tree : BFS遍历

public static String serializeBFS(TreeNode root) {
    if (root == null)
        return "#";
    String ans = "";
    Queue<TreeNode> parents = new LinkedList<>();
    parents.offer(root);
    boolean end = false;
    while (!parents.isEmpty() && !end) {
        end = true;
        int size = parents.size();
        for (int i = 0; i < size; ++i) {
            TreeNode head = parents.poll();
            // update result
            String thisnode = "";
            if (head == null) {
                thisnode = "#";
            }
            else {
                thisnode = head.value + "";
            }
            if (ans.length() == 0) {
                ans = ans + thisnode;
            }
            else {
                ans = ans + ", " + thisnode;
            }
            // update queue
            if (head != null) {
                if (!head.isLeaf())
                    end = false;
                parents.offer(head.left);
                parents.offer(head.right);
            }
        }
    }
    return ans;
}

De-serialize binary tree
~~还是直接link github代码好了.~~
试了几个方法. 最后还是觉得使用gist-it方便. 但是前提是代码不能有中文. 否则python解析不了.

Binary Tree Serialization 解题报告

题目

分析

Serialize

De-serialize

code

1. Serialize Binary Tree : BFS遍历

Comments