剑指offer:序列化二叉树

原创
2016/06/29 16:03
阅读数 273

题目

请实现两个函数,分别用来序列化和反序列化二叉树

解题

什么是序列化? 
可以理解为一直存储结构 
序列化后还要可以反序列化 
对于树的序列号,可以理解为层次遍历,但是也要记录其中的空结点,这是为了能够回去

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution3 {

    public String Serialize(TreeNode root) {
        if(root == null)
            return "";
        StringBuilder sb = new StringBuilder();
        Serialize(root, sb);
        return sb.toString();
    }

    private void Serialize(TreeNode root, StringBuilder sb) {
        if(root == null) {
            sb.append("#,");
            return;
        }
        sb.append(root.val);
        sb.append(',');
        Serialize(root.left, sb);
        Serialize(root.right, sb);
    }

    int index = -1;

   public TreeNode Deserialize(String str) {
        if(str.length() == 0)
            return null;
        String[] strs = str.split(",");
        return Deserialize(strs);
    }  

    private TreeNode Deserialize(String[] strs) {
        index++;
        if(!strs[index].equals("#")) {
            TreeNode root = new TreeNode(0);     
            root.val = Integer.parseInt(strs[index]);
            root.left = Deserialize(strs);
            root.right = Deserialize(strs);
            return root;
        }
        return null;
    }
    
    public static void main(String[] args) {
    	Solution3 s3 = new Solution3();
    	/**
    	 * 构造二叉树     
    	 *       1
    	 *      / \
    	 *     2   3
    	 *    / \ / \
    	 *   4  5 6  7
    	 */
		TreeNode root = new TreeNode(1);
		TreeNode left = new TreeNode(2);
		TreeNode right = new TreeNode(3);
		
		TreeNode left_1 = new TreeNode(4);
		TreeNode right_1 = new TreeNode(5);
		TreeNode right_2 = new TreeNode(6);
		TreeNode left_2 = new TreeNode(7);
		
		left.left = left_1;
		left.right = right_1;
		right.left = left_2;
		right.right = right_2;
		
		root.left = left;
		root.right = right;
		
		//System.out.println(s3.Serialize(root));//输出:1,2,4,#,#,5,#,#,3,7,#,#,6,#,#,
		System.out.println(s3.Deserialize("1,2,4,#,#,5,#,#,3,7,#,#,6,#,#,").left.val);//输出:2
	}
}

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
1 收藏
分享
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部