首页 > 其他分享 >Leetcode 297. 二叉树的序列化与反序列化

Leetcode 297. 二叉树的序列化与反序列化

时间:2024-09-17 13:35:30浏览次数:9  
标签:node None nodeStr 二叉树 297 序列化 节点

1.题目基本信息

1.1.题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

1.2.题目地址

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description

2.解题方法

2.1.解题思路

使用栈求二叉树的前序遍历字符串+DFS反序列化构建二叉树

2.2.解题步骤

序列化:

  • 使用栈获取二叉树的前序遍历的字符串序列(注意:需要加上None节点),加None的原因是在反序列化时提供终止递归终止条件

反序列化:

  • 第一步,将各个节点的值解析到数组中(包括None节点)
  • 第二步,使用DFS将从数组中取出节点,创建节点,并继续DFS获取左右节点的值,并创建子节点放到当前节点的左右位置

3.解题代码

Python代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        # 使用栈获取二叉树的前序遍历的字符串序列(注意:需要加上None节点),加None的原因是在反序列化时提供终止递归终止条件
        text=""
        stack=[]
        node=root
        while node or stack:
            while node:
                text+=f"{node.val},"
                stack.append(node)
                node=node.left
            text+="None,"
            node=stack.pop()
            node=node.right
        text+="None,"
        # print(text)
        return text
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        # 第一步,将各个节点的值解析到数组中(包括None节点)
        nodeStr=""
        nodeStrArr=[]
        for c in data:
            if c==",":
                nodeStrArr.append(nodeStr)
                nodeStr=""
            else:
                nodeStr+=c
        # 第二步,使用DFS将从数组中取出节点,创建节点,并继续DFS获取左右节点的值,并创建子节点放到当前节点的左右位置
        def dfs(arr):
            nodeStr=arr.pop(0)
            if nodeStr=="None":
                return None
            else:
                node=TreeNode(int(nodeStr))
                node.left=dfs(arr)
                node.right=dfs(arr)
                return node
        return dfs(nodeStrArr)

4.执行结果

在这里插入图片描述

标签:node,None,nodeStr,二叉树,297,序列化,节点
From: https://www.cnblogs.com/geek0070/p/18417107

相关文章

  • 数据结构-树和二叉树
      树和二叉树 1.树的概念   树tree     是n(n>=0)个节点的有限集    在任意的一个非空树中       (1)有且仅有一个特定的被称为根(root)的节点       (2)当n>1时,其余的节点可分为m(m>0)个互不相交的有限......
  • 代码随想录算法 - 二叉树7
    题目1669.修剪二叉搜索树给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉搜索树,使得所有节点的值在[low,high]中。修剪树不应该改变保留在树中的元素的相对结构(即,如果没有被移除,原有的父代子代关系都应当保留)。可以证明,存在唯一的答案......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树,可知,如果中间节点是p和q的公共节点,那个中间节点的数值一定在[p,q]区间因此,从根节点往下搜索,遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • leetcode刷题day20|二叉树Part08(669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索
    669.修剪二叉搜索树思路:理解了删除二叉搜索树中的节点,这个题理解起来就不难了。还是选用中序遍历递归。递归三步曲:1、传入参数:根节点,最小值,最大值;返回值为根节点;2、终止条件:如果节点为空,直接返回空;3、递归逻辑:如果最小值小于该节点,递归调用该节点的右孩子(检查右孩子......
  • leetcode刷题day19|二叉树Part07(235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的
    235.二叉搜索树的最近公共祖先思路:二叉搜索树首先考虑中序遍历。根据二叉搜索树的特性,如果p,q分别在中间节点的左右两边,该中间节点一定是最近公共祖先,如果在同一侧,则递归这一侧即可。递归三部曲:1、传入参数:根节点,p,q,返回节点。2、终止条件:因为p,q一定存在,所以不会遍历到......
  • 代码随想录算法 - 二叉树6
    题目1235.二叉搜索树的最近公共祖先给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最近公共祖先表示为一个结点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。”例如......
  • Day16 二叉树part06| LeetCode 530.二叉搜索树的最小绝对差 ,501.二叉搜索树中的众数,23
    530.二叉搜索树的最小绝对差530.二叉搜索树的最小绝对差classSolution{publicList<Integer>res=newArrayList<>();voidtraversal(TreeNoderoot){if(root==null)return;traversal(root.left);......
  • Day15 二叉树part05| LeetCode 654.最大二叉树,617.合并二叉树 ,700.二叉搜索树中的搜索
    654.最大二叉树654.最大二叉树classSolution{publicTreeNodeconstructMaximumBinaryTree(int[]nums){if(nums.length==1)//遍历到了叶子节点{returnnewTreeNode(nums[0]);}intmaxValue=nums[0......
  • Java-数据结构-二叉树-习题(二) (´▽`)ノ
    文本目录:❄️一、习题一(分层遍历):   ▶ 思路:    ▶代码:❄️二、习题二(二叉树的最近公共祖先):    ▶ 思路: ▶代码: ❄️三、习题三(从前序和中序遍历序列中构造二叉树):     ▶ 思路:  ▶代码:❄️四、习题四(从中序和后序遍历序列中构造二......
  • 使用 O(1) 额外内存删除二叉树
    这是一个naive的做法:voiddeleteTreeRec(TreeNode*root){if(root==NULL)return;deleteTreeRec(root->left);deleteTreeRec(root->right);cout<<"Deletingnode"<<root->data<<endl;deleteroot;}O(1)空......