IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Java&C++题解与拓展——leetcode449.序列化和反序列化二叉搜索树【么的新知识】 -> 正文阅读

[数据结构与算法]Java&C++题解与拓展——leetcode449.序列化和反序列化二叉搜索树【么的新知识】

每日一题做题记录，参考官方和三叶的题解

目录

题目要求

在这里插入图片描述

思路一：先序遍历

  • 用先序遍历得到序列化结果，此时第一个元素就是树的根，便于反序列化；
  • 先将序列化结果拆分成单个元素的数组，然后递归构建BST：
    • 取出当前所遍历子树的根 c u r cur cur，找到第一个比 c u r cur cur大的值，其所在下标为 j j j；
    • 所以 j j j左边都比 c u r cur cur小，为其左子树，右边都比 c u r cur cur大，为其右子树；
    • 递归构建即可。

Java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return null;
        List<String> list = new ArrayList<>();
        preOrder(root, list);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            if(i != n - 1)
                sb.append(",");
        }
        return sb.toString();
    }
    // 先序遍历
    void preOrder(TreeNode root, List<String> list) {
        if(root == null)
            return ;
        list.add(String.valueOf(root.val));
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)
            return null;
        String[] sSplit = data.split(",");
        return DFS(0, sSplit.length - 1, sSplit);
    }
    TreeNode DFS(int l, int r, String[] ss) {
        if(l > r)
            return null;
        int j = l + 1, cur = Integer.parseInt(ss[l]);
        TreeNode res = new TreeNode(cur);
        while(j <= r && Integer.parseInt(ss[j]) <= cur) // 比当前值大的第一个值
            j++;
        res.left = DFS(l + 1, j - 1, ss); // 构建左子树
        res.right = DFS(j, r, ss); // 构建右子树
        return res;
    }
}
  • 时间复杂度：序列化复杂度为 O ( n ) O(n) O(n)，其中 n n n为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为 O ( n 2 ) O(n^2) O(n2)，为一条向左下方延伸的链。
  • 空间复杂度： O ( n ) O(n) O(n)

C++

【注意地址符】

class Codec {
public:
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<string> list;
        preOrder(root, list);
        if(list.size() == 0)
            return "";
        string res;
        for(int i = 0; i < list.size() - 1; i++)
            res.append(list[i] + ",");
        res.append(list.back());
        return res;
    }
    // 先序遍历
    void preOrder(TreeNode* root, vector<string> &list) {
        if(root == nullptr)
            return ;
        list.emplace_back(to_string(root->val));
        preOrder(root->left, list);
        preOrder(root->right, list);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 0)
            return nullptr;
        vector<string> sSplit = split(data);
        return DFS(0, sSplit.size() - 1, sSplit);
    }
    TreeNode* DFS(int l, int r, vector<string> &ss) {
        if(l > r)
            return nullptr;
        int j = l + 1, cur = stoi(ss[l]);
        TreeNode* res = new TreeNode(cur);
        while(j <= r && stoi(ss[j]) <= cur) // 比当前值大的第一个值
            j++;
        res->left = DFS(l + 1, j - 1, ss); // 构建左子树
        res->right = DFS(j, r, ss); // 构建右子树
        return res;
    }
    // 以“，”分割字符串
    vector<string> split(const string &str) {
        char dec = ',';
        int pos = 0;
        int start = 0;
        vector<string> res;
        while(pos < str.size()) {
            while(pos < str.size() && str[pos] == dec)
                pos++;
            start = pos;
            while(pos < str.size() && str[pos] != dec)
                pos++;
            if(start < str.size())
                res.emplace_back(str.substr(start, pos - start));
        }
        return res;
    }
};
  • 时间复杂度：序列化复杂度为 O ( n ) O(n) O(n)，其中 n n n为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为 O ( n 2 ) O(n^2) O(n2)，为一条向左下方延伸的链。
  • 空间复杂度： O ( n ) O(n) O(n)

思路二：二分查找

  • 和上面一样，只不过在反序列化时，采用二分查找第一个大于当前值的位置。

Java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return null;
        List<String> list = new ArrayList<>();
        preOrder(root, list);
        int n = list.size();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(list.get(i));
            if(i != n - 1)
                sb.append(",");
        }
        return sb.toString();
    }
    // 先序遍历
    void preOrder(TreeNode root, List<String> list) {
        if(root == null)
            return ;
        list.add(String.valueOf(root.val));
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)
            return null;
        String[] sSplit = data.split(",");
        return DFS(0, sSplit.length - 1, sSplit);
    }
    TreeNode DFS(int l, int r, String[] ss) {
        if(l > r)
            return null;
        int ll = l + 1, rr = r, cur = Integer.parseInt(ss[l]);
        while(ll < rr) { // 二分找第一个大于当前值
            int m = ll + rr >> 1;
            if(Integer.parseInt(ss[m]) > cur)
                rr = m;
            else
                ll = m + 1;            
        }
        if(Integer.parseInt(ss[rr]) <= cur)
            rr++;
        TreeNode res = new TreeNode(cur);
        res.left = DFS(l + 1, rr - 1, ss); // 构建左子树
        res.right = DFS(rr, r, ss); // 构建右子树
        return res;
    }
}
  • 时间复杂度：序列化复杂度为 O ( n ) O(n) O(n)，其中 n n n为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为 O ( n log ? n ) O(n\log n) O(nlogn)，为一条向左下方延伸的链。
  • 空间复杂度： O ( n ) O(n) O(n)

C++

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<string> list;
        preOrder(root, list);
        if(list.size() == 0)
            return "";
        string res;
        for(int i = 0; i < list.size() - 1; i++)
            res.append(list[i] + ",");
        res.append(list.back());
        return res;
    }
    // 先序遍历
    void preOrder(TreeNode* root, vector<string> &list) {
        if(root == nullptr)
            return ;
        list.emplace_back(to_string(root->val));
        preOrder(root->left, list);
        preOrder(root->right, list);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 0)
            return nullptr;
        vector<string> sSplit = split(data);
        return DFS(0, sSplit.size() - 1, sSplit);
    }
    TreeNode* DFS(int l, int r, vector<string> &ss) {
        if(l > r)
            return nullptr;
        int ll = l + 1, rr = r, cur = stoi(ss[l]);
        while(ll < rr) { // 二分找第一个大于当前值
            int m = (ll + rr) >> 1;
            if(stoi(ss[m]) > cur)
                rr = m;
            else
                ll = m + 1;
        }

        if(stoi(ss[rr]) <= cur) // 比当前值大的第一个值
            rr++;
        TreeNode* res = new TreeNode(cur);
        res->left = DFS(l + 1, rr - 1, ss); // 构建左子树
        res->right = DFS(rr, r, ss); // 构建右子树
        return res;
    }
    // 以“，”分割字符串
    vector<string> split(const string &str) {
        char dec = ',';
        int pos = 0;
        int start = 0;
        vector<string> res;
        while(pos < str.size()) {
            while(pos < str.size() && str[pos] == dec)
                pos++;
            start = pos;
            while(pos < str.size() && str[pos] != dec)
                pos++;
            if(start < str.size())
                res.emplace_back(str.substr(start, pos - start));
        }
        return res;
    }
};
  • 时间复杂度：序列化复杂度为 O ( n ) O(n) O(n)，其中 n n n为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为 O ( n log ? n ) O(n\log n) O(nlogn)，为一条向左下方延伸的链。
  • 空间复杂度： O ( n ) O(n) O(n)

思路三：后序遍历+栈

java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)
            return null;
        List<String> list = new ArrayList<>();
        postOrder(root, list);
        int n = list.size();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(list.get(i));
            if(i != n - 1)
                sb.append(",");
        }
        return sb.toString();
    }
    // 后序遍历
    void postOrder(TreeNode root, List<String> list) {
        if(root == null)
            return ;
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(String.valueOf(root.val));
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)
            return null;
        String[] sSplit = data.split(",");
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for(int i = 0; i < sSplit.length; i++)
            stack.push(Integer.parseInt(sSplit[i]));
        return DFS(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
    }
    TreeNode DFS(int low, int up, Deque<Integer> stack) {
        if(stack.isEmpty() || stack.peek() < low || stack.peek() > up)
            return null;
        int cur = stack.pop();
        TreeNode res = new TreeNode(cur);
        res.right = DFS(cur, up, stack); // 更大的值构建右子树
        res.left = DFS(low, cur, stack); // 更小的值构建左子树
        return res;
    }
}
  • 时间复杂度：序列化和反序列化均为 O ( n ) O(n) O(n)
  • 空间复杂度： O ( n ) O(n) O(n)

C++

class Codec {
public:
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<string> list;
        postOrder(root, list);
        if(list.size() == 0)
            return "";
        string res;
        for(int i = 0; i < list.size() - 1; i++)
            res.append(list[i] + ",");
        res.append(list.back());
        return res;
    }
    // 后序遍历
    void postOrder(TreeNode* root, vector<string> &list) {
        if(root == nullptr)
            return ;
        postOrder(root->left, list);
        postOrder(root->right, list);
        list.emplace_back(to_string(root->val));
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 0)
            return nullptr;
        vector<string> sSplit = split(data);
        stack<int> stack;
        for(auto &s : sSplit)
            stack.emplace(stoi(s));
        return DFS(INT_MIN, INT_MAX, stack);
    }
    TreeNode* DFS(int low, int up, stack<int>& stack) {
        if(stack.size() == 0 || stack.top() <low || stack.top() > up)
            return nullptr;
        int cur = stack.top();
        stack.pop();
        TreeNode* res = new TreeNode(cur);
        res->right = DFS(cur, up, stack); // 更大的值构建右子树
        res->left = DFS(low, cur, stack); // 更小的值构建左子树
        return res;
    }
    // 以“，”分割字符串
    vector<string> split(const string &str) {
        char dec = ',';
        int pos = 0;
        int start = 0;
        vector<string> res;
        while(pos < str.size()) {
            while(pos < str.size() && str[pos] == dec)
                pos++;
            start = pos;
            while(pos < str.size() && str[pos] != dec)
                pos++;
            if(start < str.size())
                res.emplace_back(str.substr(start, pos - start));
        }
        return res;
    }
};
  • 时间复杂度：序列化和反序列化均为 O ( n ) O(n) O(n)
  • 空间复杂度： O ( n ) O(n) O(n)

总结

一道快乐的递归遍历题~

【补觉day，最近拖延症发作】


欢迎指正与讨论！
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-13 11:54:55  更:2022-05-13 11:55:59 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 4:32:53-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码