微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 37.序列化二叉树

剑指offer 37.序列化二叉树

题目描述

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

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

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

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

题解

(DFS) O(n)

【1】序列化：前序遍历二叉树，对于空节点序列化为 #，对于非空节点将将值转换为字符串，每个节点之间用 , 隔开，为了反序列化判断节点边界。

【2】反序列化：根据一颗二叉树的前序序列中的非空节点和空节点可以反序列化出原二叉树。

  1. 递归函数含义：TreeNode* d_dfs(string& s, int& u) u 表示遍历到字符串 s 的哪个位置了
  2. 递归出口条件：当字符串的所有节点都处理完自动结束
  3. 单层递归逻辑：
    • 如果当前字符是 #​，则表示是空节点，直接返回空节点即可。
    • 否则是非空节点，找出非空节点的连续值（注意：可能是多位数，或者包括负号）
    • 创建当前节点，并递归创建它的左儿子和右儿子
    • 最后返回当前节点 最后 deserialize() 中返回的就是二叉树的根节点

时间复杂度

O(n)，每个节点只会被遍历一次。

空间复杂度

O(n)，序列化后的字符串。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    string s;

    void s_dfs(TreeNode* root) {
        if (!root) {
            s += "#,";
            return;
        }

        s += to_string(root->val) + ',';
        s_dfs(root->left);
        s_dfs(root->right);
    }
    
    string serialize(TreeNode* root) {
        if (!root) return s;
        s_dfs(root);
        return s;
    }

    TreeNode* d_dfs(string& s, int& u) {
        if (s[u] == '#') {
            u += 2;
            return nullptr;
        }
        
        // 判断负号
        bool is_minus = false; 
        if (s[u] == '-') is_minus = true, u ++ ;
        int k = u;
        int val = 0;
        while (k < s.size() && s[k] != ',') val = val * 10 + (s[k ++ ] - '0');
        if (is_minus) val = -val;
        
        k ++ ;
        u = k;
        auto root = new TreeNode(val);
        root->left = d_dfs(s, u);
        root->right = d_dfs(s, u);
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        cout << data << endl;
        int u = 0;
        return d_dfs(data, u);
    }
};

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    
    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
    
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        Queue<String> queue = new LinkedList<>(Arrays.asList(nodes));
        return deserialize(queue);
    }
    
    private TreeNode deserialize(Queue<String> queue) {
        String val = queue.poll();
        if (val.equals("#")) {
            return null;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

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: TreeNode) -> str:
        if not root:
            return '#,'
        
        return str(root.val) + ',' + self.serialize(root.left) + self.serialize(root.right)

    def deserialize(self, data: str) -> TreeNode:
        nodes = data.split(',')
        queue = collections.deque(nodes)
        return self.deserialize_helper(queue)
    
    def deserialize_helper(self, queue):
        val = queue.popleft()
        if val == '#':
            return None
        
        node = TreeNode(int(val))
        node.left = self.deserialize_helper(queue)
        node.right = self.deserialize_helper(queue)
        return node
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer