剑指offer—序列化二叉树 解答

剑指offer—序列化二叉树

题目描述

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

二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。
二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

思路

  • 序列化、反序列化可以使用二叉树等多种遍历方式,我们选取前序遍历,使用递归较为简单

序列化

使用一个全局String对象接收序列化结果

  • 如果节点为空,在后面插入一个#
  • 节点不为空,插入节点的val,再在后面插入一个

反序列化

使用一个全局int值p作为当前遍历到的序列化String中对应char的下标,初始传入为0

  • 如果当前传入的位置大于序列化String的长度,返回null
  • 如果当前字符为#,返回null节点
  • 否则说明当前字符属于一个节点的值,但是有可能该节点值长度超过1,我们需要继续往后扫描,加到一个整数中,技巧如下
int val = 0;
while(s.charAt(p)!='!'){
    val = val * 10 + (s.charAt(p++) - '0');//往后扫描,每次×10进位,char转int需要-'0',char存储的是ascii码
}
  • 继续递归遍历完成一个节点和左右子树的反序列化
TreeNode root = new TreeNode(val);
root.left = pre_dfs(s,p+1);
root.right = pre_dfs(s,p+1);

代码

public class Solution {
       String res = "";
       String Serialize(TreeNode root) {
            dfs_pre(root);
            return res;
        }
        public void dfs_pre(TreeNode node){
            if(node==null) {
                res += "#"; 
                return ;
            }
            res += node.val+"!";
            dfs_pre(node.left);
            dfs_pre(node.right);
        }

        TreeNode Deserialize(String str) {
            return pre_dfs(str,0);
        }
        int p = 0;
        public TreeNode pre_dfs(String s,int n){
            if(n>=s.length()) return null;
            p = n;
            if(s.charAt(n)=='#') return null;
            int val = 0;
            while(s.charAt(p)!='!'){
                val = val * 10 + (s.charAt(p++) - '0');
            }
            TreeNode root = new TreeNode(val);
            root.left = pre_dfs(s,p+1);
            root.right = pre_dfs(s,p+1);
            return root;
        }
}