栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指offer 50. 序列化二叉树-java

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer 50. 序列化二叉树-java

Acwing 50. 序列化二叉树 原题链接

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

您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。

数据范围
树中节点数量 [0,1000]。

代码案例:


前序遍历也可以 不局限于层序遍历

题解

class Solution {
   // import java.util.*;
    int u = 0 ;
     
    StringBuilder res = new StringBuilder();
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        
        dfs(root,res);
          
        return res.toString() ;
    }
   void dfs(TreeNode root,StringBuilder res){
        if(root == null) {
             res.append("null,"); 
             return  ;
        }
       res.append(root.val) ;
       res.append(',') ;
       dfs(root.left,res);
       dfs(root.right,res);
       //  System.out.println(res);
    }
    // Decodes your encoded data to tree.
    TreeNode deserialize(String s) {
        return dfs_d(s);
    }
    TreeNode dfs_d(String s ){
        if(u == s.length()) return null; //如果已经达到了字符串的尾端,则退出。
        int k = u ;
         while (s.charAt(k) != ',') k ++ ;
         if(s.charAt(u) == 'n'){//如果当前字符串是“null”
             u = k + 1 ;//回到下一个数字的首部,注意是u = k+1, 不是u = u+1;
             return null;
         }
         int val = 0 ;
         int sign = 1;
         if (u < k && s.charAt(u) == '-') {
             sign = -1; u ++ ;//如果是负数  则下一位  
         }
        for (int i = u; i < k; i ++ ) val = val * 10 + s.charAt(i) - '0';//把字符串转化为数字
        val = val*sign;
         u = k + 1;//回到下个数字的首部
         
        //递归算法总是先写退出条件,然后才递归调用。
        TreeNode root = new TreeNode(val);
        root.left = dfs_d(s);
        root.right = dfs_d(s);
        return root;
    }
}

class Solution {

    int index = -1;
    // Encodes a tree to a single string.
    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root==null) {
            sb.append("null,");
            return sb.toString();
        }

        sb.append(root.val).append(",");
        sb.append(serialize(root.left));
        sb.append(serialize(root.right));
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    TreeNode deserialize(String data) {
        index++;
        String[] nodes = data.split(",");
        TreeNode node = null;
        if(!nodes[index].equals("null")){
            node = new TreeNode(Integer.valueOf(nodes[index]));
            node.left = deserialize(data);
            node.right = deserialize(data);
        }
        return node;

    }
}

 
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/952932.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号