题解 | 二叉树的序列化

解题思路

这是一个二叉树序列化问题，使用括号序列表示二叉树结构。每个节点用一对括号表示，其中包含左右子树的括号序列。

关键点：

使用括号表示每个节点
递归处理左右子树
使用字符流处理字符串拼接
按照前序遍历顺序生成序列

算法步骤：

处理空节点情况
添加左括号
递归处理左右子树
添加右括号

代码

cpp
java
python

class TreeToSequence {
public:
    string toSequence(TreeNode* root) {
        if (!root) {
            return "";
        }
        
        ostringstream oss;
        oss << '(';
        
        if (root->left) {
            oss << toSequence(root->left);
        }
        
        if (root->right) {
            oss << toSequence(root->right);
        }
        
        oss << ')';
        return oss.str();
    }
};

import java.util.*;

public class TreeToSequence {
    public String toSequence(TreeNode root) {
        if (root == null) {
            return "";
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append('(');
        
        if (root.left != null) {
            sb.append(toSequence(root.left));
        }
        
        if (root.right != null) {
            sb.append(toSequence(root.right));
        }
        
        sb.append(')');
        return sb.toString();
    }
}

class TreeToSequence:
    def toSequence(self, root):
        if not root:
            return ""
            
        result = ['(']
        
        if root.left:
            result.append(self.toSequence(root.left))
            
        if root.right:
            result.append(self.toSequence(root.right))
            
        result.append(')')
        return "".join(result)

算法及复杂度

算法：递归
时间复杂度： $\mathcal{O(n)}$ ，每个节点访问一次
空间复杂度： $\mathcal{O(h)}$ ， $h$ 是树的高度，递归栈的深度