Leetcode - Serialize and Deserialize Binary Tree

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

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { 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() - 1);
    }
    
    private void dfs(StringBuilder ret, TreeNode root) {
        if (root == null) {
            ret.append("n;");
            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() == 0)
            return null;
        String[] treeArr = data.split(";");
        return ddfs(treeArr);
    }
    
    private TreeNode ddfs(String[] treeArr) {
        if (curr < 0 || curr >= treeArr.length)
            return null;
        String word = treeArr[curr];
        curr++;
        if (word.equals("n")) { // null node
            return null;
        }
        else {
            int val = Integer.parseInt(word);
            TreeNode root = new TreeNode(val);
            root.left = ddfs(treeArr);
            root.right = ddfs(treeArr);
            return root;
        }
    }
}

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

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

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

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

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

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

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

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

   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(val);
           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;
   }

然后这篇文章的衍生版讨论了,采用非递归来恢复。
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/

有时间再看下吧。

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

My code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { 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(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = q.poll();
                if (temp == null) {
                    ret.append("n,");
                    continue;
                }
                ret.append(temp.val + ",");
                q.offer(temp.left);
                q.offer(temp.right);
            }
        }
        
        String retStr = ret.toString();
        return retStr.substring(0, retStr.length() - 1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0)
            return null;
        String[] treeArr = data.split(",");
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(treeArr[0]));
        q.offer(root);
        int i = 1;
        while (i < treeArr.length) {
            TreeNode temp = q.poll();
            if (!treeArr[i].equals("n")) {
                int val = Integer.parseInt(treeArr[i]);
                temp.left = new TreeNode(val);
                q.offer(temp.left);
            }
            i++;
            if (!treeArr[i].equals("n")) {
                int val = Integer.parseInt(treeArr[i]);
                temp.right = new TreeNode(val);
                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(root));

其实一共有两个数据结构。
首先是一个队列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

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

参考网页:
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/

当树结点是 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(i, ...
);
   }
}

**
复杂度是,O(2 ^ n)

第二种,类似于

  1. Generate Parentheses -
    http://www.jianshu.com/p/2c9e588def78
    的思想。
    分成两种情况dfs
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(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }
    
    private void dfs(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("X,");
        }
        else {
            sb.append(root.val).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() != 0) {
                q.offer(parts[i]);
            }
        }
        
        return ddfs(q);
    }
    
    private TreeNode ddfs(Queue<String> q) {
        String s = q.poll();
        if (s.equals("X")) {
            return null;
        }
        else {
            TreeNode root = new TreeNode(Integer.parseInt(s));
            root.left = ddfs(q);
            root.right = ddfs(q);
            return root;
        }
    }
}

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

reference:
https://discuss.leetcode.com/topic/28029/easy-to-understand-java-solution/2

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

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

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

于是有个题:
给你一个 BST 的 preorder / postorder 序列,恢复出这个BST
pre-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(val);
        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(val);
        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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容