图片 1Screenshot
from 2016-02-13 16:26:04.png

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "";
        Queue<TreeNode> queue=new LinkedList<>();
        StringBuilder res=new StringBuilder();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur==null){
                res.append("n ");
                continue;
            }
            res.append(cur.val+" ");
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data=="") return null;
        Queue<TreeNode> queue=new LinkedList<>();
        String[] values=data.split(" ");
        TreeNode root=new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);
        for(int i=1;i<values.length;i++){
            TreeNode cur=queue.poll();
            if(!values[i].equals("n")){
                TreeNode left=new TreeNode(Integer.parseInt(values[i]));
                cur.left=left;
                queue.offer(left);
            }
            if (!values[++i].equals("n")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                cur.right = right;
                queue.add(right);
            }
        }
        return root;
    }
}

二叉树的序列化和反序列化。我一开始想用BFS的,但第一不知道怎么处理空子树,第二不知道怎么还原一棵树。于是照着solutions的高票答案写了一遍。

Serialization is the process of converting a data structure or object
into a sequence of bits so that it can be stored in a file or memory
buffer, or transmitted across a network connection link to be
reconstructed later in the same or another computer environment.

原题

设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。

样例,给出一个测试数据样例,
二叉树{3,9,20,#,#,15,7},表示如下的树结构:

  3
 / \
9  20
  /  \
 15   7

My code:

Approach 1 : preorder traverse(dfs)

    1
   / \
  2   3
     / \
    4   5

对于上面这棵树,这种方法会把它serialize成"1,2,X,X,3,4,X,X,5,X,X,"这样的字符串。也就是preorder地遍历。buildTree的过程也是递归,跟serialize的过程其实就是相反的。递归构造一棵树的方法还是值得注意的。

    private static final String spliter = ",";
    private static final String NN = "X";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    private void preorder(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(spliter);
            return;
        }
        sb.append(node.val).append(spliter);
        preorder(node.left, sb);
        preorder(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(data.split(spliter)));
        //如何返回root:递归返回的最终就是root
        return buildTree(queue);
    }

    private TreeNode buildTree(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals(NN)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = buildTree(queue);
        node.right = buildTree(queue);

        return node;
    }

问了同举,他让我用Gson.toJson试一下。

Design an algorithm to serialize and deserialize a binary tree. There is
no restriction on how your serialization/deserialization algorithm
should work. You just need to ensure that a binary tree can be
serialized to a string and this string can be deserialized to the
original tree structure.

解题思路

  • 序列化:Recursion –
    先序遍历,null用#代替,上面的例子先序遍历后成为[3, 9, #, #, 20,
    15, #, #, 7, #, #]
  • 反序列化: 根据[3, 9, #, #, 20, 15, #, #, 7, #,
    #]反序列化,采用先序遍历的思想每次读取一个结点,如果读取到#,忽略。如果读取到结点数值,则插入到当前结点,然后遍历左孩子和右孩子。
  • BFS,二叉树的层次遍历, 序列化为[3, 9, 20, #, #, 15, 7, #, #,
    #, #]
  • Python中的两个内置函数 – iter() 和 next()
  • iter() takes an iterable object and returns an iterator.
  • Each time we call the next() method on the iterator gives us the
    next element.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Codec { public String serialize(TreeNode root) { if (root == null) return null; StringBuilder ret = new StringBuilder(); dfs(ret, root); String retStr = ret.toString(); return retStr.substring(0, retStr.length; } private void dfs(StringBuilder ret, TreeNode root) { if (root == null) { ret.append; return; } int val = root.val; ret.append(val + ";"); dfs(ret, root.left); dfs(ret, root.right); } // Decodes your encoded data to tree. private int curr = 0; public TreeNode deserialize(String data) { if (data == null || data.length return null; String[] treeArr = data.split; return ddfs; } private TreeNode ddfs(String[] treeArr) { if (curr < 0 || curr >= treeArr.length) return null; String word = treeArr[curr]; curr++; if (word.equals { // null node return null; } else { int val = Integer.parseInt; TreeNode root = new TreeNode; root.left = ddfs; root.right = ddfs; return root; } }}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.deserialize(codec.serialize;

Approach 2 : BFS

For example, you may serialize the following tree

完整代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        def dfs(node):
            if node:
                res.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
            else:
                res.append("#")
        res = []
        dfs(root)
        return ' '.join(res)


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 0:
            return None
        def dfs():
            val = next(res)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        res = iter(data.split())
        return dfs()



# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

这个类型的题目以前从来没有碰到过。可以分成两块: serialize 和
deserialize类似于encode 和
decode加密的方式有哪些?递归或者非递归。pre-order,
post-orderORlevel-order

我先去看电影了。

bfs的解法会把上面的tree序列化成:"1 2 3 n n 4 5 n n n n "这样。理解起来其实更容易。serialize的过程就是level
order traverse的过程,注意null的处理。build
tree的过程是把null跳过不接到parent上。

    //BFS
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        StringBuilder res = new StringBuilder();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("n ");
                continue;
            }
            res.append(node.val + " ");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        Queue<TreeNode> q = new LinkedList<>();
        String[] values = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("n")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                q.add(left);
            }
            if (!values[++i].equals("n")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                q.add(right);
            }
        }
        return root;
    }

摘抄:
【注意】
1、不要幻想不用分隔符(我用的是“,”),没有分隔符对于1位以上的数是区分不了的。比如345,你觉得是1个数345还是分别3个数呢?(这就是我愚蠢的地方,耗费我数小时思考)

2、String的split方法有个坑:
对于”11,12,13,”,用data.split(“,”)可以得到正确结果;但是”,11,12,13″split后得到的是null。所以分隔符要放后面

这题还有个follow up:449. Serialize and Deserialize BST
,用这题的代码也可以过,但是没用到BST的性质。看了下那题的答案,不是很懂deserialization的过程。


ref:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/\#/solutions
http://www.jianshu.com/p/18578f767668
http://blog.csdn.net/byamao1/article/details/53086548

    1
   / \
  2   3
     / \
    4   5

第一个解法采用的是 pre-order先序遍历整棵树,然后数字就翻译成 val + “,”
空指针就翻译成 “n,”然后一系列处理过后,完成工作。

as

难点在于deserialize类似于,给你一个
pre-order的访问顺序的数组,恢复出这个普通的,general binary tree.

"[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes
a binary
tree.
You do not necessarily need to follow this format, so please be creative
and come up with different approaches yourself.

依旧采用dfs设置一个全局变量 curr = 0然后,每次进入dfs中时,

Note:

curr++;if (treeArr[curr].equals {...}else { TreeNode root = new TreeNode; root.left = dfs; root.right = dfs; return root;}

Do not use class member/global/static variables to store states. Your
serialize and deserialize algorithms should be stateless.

因为 pre-order时,每个sub
tree的头结点一定出现在该范围数组的最左侧。最左侧的左子树,也一定出现在数组的最左侧。所以curr不断往右移,当碰到null时,不再递归。相当于从左侧开始,把整个binary
tree慢慢做了出来。意会下。复杂度是O也正好差不多对应了一道题目,给你一个pre-order
array,
恢复出一个BST

Friend: 449. Serialize and Deserialize BST

也是用的相同的思想。对于这道题木,My code:

Solution:Preorder 序列化 + 单queue 递归反序列化

思路:

图片 2

Screen Shot 2017-12-01 at 21.43.47.png

BT方法:BT/BST通用,稍废Space,但Time:O(N)
BST方法:BST独用(根据BST特性),可省Space,但Time for
Deserialize最差有可能:O(N^2)

Time Complexity: O(N) Space Complexity: O(N)

Solution Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private static final String SEP = ",";
    private static final String NN = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        System.out.println("String: " + sb.toString());
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(SEP);
        } else {
            sb.append(node.val).append(SEP);
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) return null;

        Queue<String> queue = new LinkedList<>();
        String[] strs = data.split(SEP);
        for (String e : strs) {
            queue.offer(e);
        }

        return buildTree(queue);
    }

    private TreeNode buildTree(Queue<String> queue) {
        if (queue.isEmpty()) return null;
        String val = queue.poll();
        if (val.equals(NN)) return null;
        else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(queue);
            node.right = buildTree(queue);
            return node;
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
 private int begin = 0; public TreeNode formBST(int[] nums) { if (nums == null || nums.length == 0) return null; return dfs(nums, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode dfs(int[] nums, int min, int max) { if (begin >= nums.length) return null; int val = nums[begin]; if (val > min && val < max) { begin++; TreeNode root = new TreeNode; root.left = dfs(nums, min, val); root.right = dfs(nums, val, max); return root; } return null; }

全局变量begin可以用一个 private class Index 来代替,将Index
每次作为参数做递归。这样每次变化的值都可以存下来。

然后也可以通过 post-order 恢复。差不多的原理。My code:

 private int end = 0; public TreeNode formBST(int[] nums) { if (nums == null || nums.length == 0) return null; end = nums.length - 1; return ddfs(nums, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode ddfs(int[] nums, int min, int max) { if (end < 0) return null; if (nums[end] > min && nums[end] < max) { TreeNode root = new TreeNode(nums[end]); end--; root.right = ddfs(nums, root.val, max); root.left = ddfs(nums, min, root.val); return root; } else return null; }

然后这篇文章的衍生版讨论了,采用非递归来恢复。

有时间再看下吧。

然后再说下,serialize and deserialize 的第二种方法,非递归,采用队列 +
层序遍历的方法。

My code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) return null; Queue<TreeNode> q = new LinkedList<TreeNode>(); StringBuilder ret = new StringBuilder(); q.offer; while (!q.isEmpty { int size = q.size(); for (int i = 0; i < size; i++) { TreeNode temp = q.poll(); if (temp == null) { ret.append; continue; } ret.append(temp.val + ","); q.offer(temp.left); q.offer(temp.right); } } String retStr = ret.toString(); return retStr.substring(0, retStr.length; } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data == null || data.length return null; String[] treeArr = data.split; Queue<TreeNode> q = new LinkedList<TreeNode>(); TreeNode root = new TreeNode(Integer.parseInt(treeArr[0])); q.offer; int i = 1; while (i < treeArr.length) { TreeNode temp = q.poll(); if (!treeArr[i].equals { int val = Integer.parseInt(treeArr[i]); temp.left = new TreeNode; q.offer(temp.left); } i++; if (!treeArr[i].equals { int val = Integer.parseInt(treeArr[i]); temp.right = new TreeNode; q.offer(temp.right); } i++; } return root; }}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.deserialize(codec.serialize;

其实一共有两个数据结构。首先是一个队列queue,用于存放 parent
node然后数列访问的正好是其 左右孩子结点。所以每次都要判断 arr[i] and
arr[i +
1]因为加密的时候,对于非null的结点,就一定会保存其左右孩子结点的信息,哪怕他们使null。所以解密的时候,采用队列的方式。每次从队列里面弹出来的结点,其左右孩子的信息正好存在当前
treeArr[i] and treeArr[i + 1] 里面。

然后还有一些优化的余地。因为leaf node 都跟着两个null
的左右孩子,浪费了加密信息的空间。可以分成 internal node and external
node

图片 3Screenshot
from 2016-02-13 20:41:16.png

参考网页:

当树结点是 linked list
时,也可以通过这个层序遍历来实现。只不过,加密的时候必须要注明其儿子结点的个数node
value / number of child nodes然后,binary tree中是访问 i , i +
1这里就是访问,for (int j = i, j < i + n; j++) {…}

**这道题目里面牵扯到了许多我以前没有关注过的地方。给你一个pre-order or
post-order array, 恢复出BST或者给你一个含有value和null 的string array,
恢复出binary tree然后递归的方法,非递归的方法。

对于这种dfs,我也是第一次碰到。目前能够想到的dfs有三种。第一种,类似于
combination, permutation 那类题目的

dfs() { if (special case) {.... return....} else { for (int i = begin; i < end; i++) { dfs; }}

**复杂度是,O

第二种,类似于

  1. Generate Parentheses

if  { dfs; }else { dfs; }

复杂度暂时想不清楚。

第三种,就是这道题目里面的dfs设置一个index一步一步移动。

if  {...}else { dfs; dfs;}

这种将binary tree serialize的做法,在web
programming里面,应该很常见的,虽然到目前为止我还没有碰到过。但这的确是对树的三种遍历加层序遍历的最好应用。

Anyway, Good luck, Richardo!

My code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); dfs; return sb.toString(); } private void dfs(TreeNode root, StringBuilder sb) { if (root == null) { sb.append; } else { sb.append.append; dfs(root.left, sb); dfs(root.right, sb); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] parts = data.split; Queue<String> q = new LinkedList<String>(); for (int i = 0; i < parts.length; i++) { if (parts[i].length { q.offer; } } return ddfs; } private TreeNode ddfs(Queue<String> q) { String s = q.poll(); if (s.equals { return null; } else { TreeNode root = new TreeNode(Integer.parseInt; root.left = ddfs; root.right = ddfs; return root; } }}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.deserialize(codec.serialize;

reference:

思路主要就是, pre-order 遍历一棵树,同时标识出空节点。然后 decode
的时候,恢复出这个binary tree

那么,什么情况下可以恢复呢?

1 . pre-order / post-order + 标识出空节点2 . pre-order / post-order +
binary search tree

于是有个题:给你一个 BST 的 preorder / postorder
序列,恢复出这个BSTpre-order

private int counter_Pre = 0;public TreeNode restoreBST_Pre(int[] nums) { return helper_Pre(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);}private TreeNode helper_Pre(int[] nums, int min, int max) { if (counter_Pre >= nums.length) { return null; } int val = nums[counter_Pre]; if (val > min && val < max) { counter_Pre++; TreeNode root = new TreeNode; root.left = helper_Pre(nums, min, val); root.right = helper_Pre(nums, val, max); return root; } return null;}

post-order

int counter_Post;public TreeNode restoreBST_Post(int[] nums) { counter_Post = nums.length - 1; return helper_Post(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);} private TreeNode helper_Post(int[] nums, int min, int max) { if (counter_Post < 0) { return null; } int val = nums[counter_Post]; if (min < val && val < max) { counter_Post--; TreeNode root = new TreeNode; root.right = helper_Post(nums, val, max); root.left = helper_Post(nums, min, val); return root; } return null;}

Anyway, Good luck, Richardo! — 09/23/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图