南昌做购物网站的公司,mc做弊端网站,网站建设用什么软件做,昆明网建剑指 Offer#xff08;第2版#xff09;面试题 37#xff1a;序列化二叉树 剑指 Offer#xff08;第2版#xff09;面试题 37#xff1a;序列化二叉树解法1#xff1a;深度优先搜索 剑指 Offer#xff08;第2版#xff09;面试题 37#xff1a;序列化二叉树
题目来源… 剑指 Offer第2版面试题 37序列化二叉树 剑指 Offer第2版面试题 37序列化二叉树解法1深度优先搜索 剑指 Offer第2版面试题 37序列化二叉树
题目来源50. 序列化二叉树
解法1深度优先搜索
使用 stringstream 流会很方便。
二叉树可以序列化为字符串
若节点不为空将节点的 val 直接送入流如果遇到空指针将字符串 “null” 送入流流中节点之间用一个空格区分。深度优先遍历二叉树即可。
字符串反序列化为原始树结构
每次从流中取出一个字符串 t当 t 为 “null” 时返回空结点。否则令 val stoi(t)以 val 为值建立一个新结点递归建立它的左子树和右子树。
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution
{
public:// Encodes a tree to a single string.string serialize(TreeNode *root){if (root nullptr)return ;stringstream ss;dfs_serialize(root, ss);return ss.str();}// 辅函数 - 深度优先搜索建立流void dfs_serialize(TreeNode *root, stringstream ss){if (root nullptr)ss null ;else{ss root-val ;dfs_serialize(root-left, ss);dfs_serialize(root-right, ss);}}// Decodes your encoded data to tree.TreeNode *deserialize(string data){if (data.empty())return nullptr;stringstream ss(data);return dfs_deserialize(ss);}// 辅函数 - 根据流递归建立二叉树TreeNode *dfs_deserialize(stringstream ss){string t;ss t;if (t null)return nullptr;int val stoi(t);TreeNode *root new TreeNode(val);root-left dfs_deserialize(ss);root-right dfs_deserialize(ss);return root;}
};复杂度分析
时间复杂度O(n)其中 n 是二叉树的节点个数。每个节点都会遍历一次。
空间复杂度O(depth)其中 depth 是二叉搜索树的深度。
