二叉树转字符串的递归实现与边界处理详解

二叉树转字符串的递归实现与边界处理详解

将二叉树结构转化为特定格式的字符串是算法面试中的常见考点。这道题不仅考察对二叉树遍历的理解，更考验对递归逻辑和边界条件的处理能力。

核心思路

我们需要按照'根节点 (左子树)(右子树)'的格式生成字符串。这里有两条关键规则：

1. 若左子树为空但右子树非空，需保留左子树的空括号 ()。
2. 若右子树为空，可直接省略其括号。

实现上采用前序递归遍历：先处理根节点，再递归处理左子树，最后递归处理右子树。在遍历过程中根据左右子树的存在情况，动态添加括号并处理边界条件。

代码实现

为了高效拼接字符，我们使用 StringBuilder。主方法负责初始化，辅助递归方法负责具体的节点处理和括号逻辑。

public String tree2str(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    dfs(root, sb);
    return sb.toString();
}

private void dfs(TreeNode node, StringBuilder sb) {
    if (node == null) {
        return;
    }

    // 1. 处理当前节点值
    sb.append(node.val);

    // 2. 处理左子树
    if (node.left != null) {
        sb.append("(");
        dfs(node.left, sb);
        sb.append(")");
    } else if (node.right != null) {
        // 左空右非空，必须补空括号
        sb.append("()");
    }

    // 3. 处理右子树
    if (node.right != null) {
        sb.append("(");
        dfs(node.right, sb);
        sb.append(")");
    }
}

关键点解析

这段代码最微妙的地方在于左子树为空的判断。如果直接忽略左子树，当遇到 [1, null, 2] 这种结构时，生成的字符串会变成 1(2)，而正确结果应该是 。因此，必须在左子树为空时检查右子树是否存在，以此决定是否插入空括号。