606. Construct String From Binary Tree

Easy

Description

給定一棵二元樹，用前序遍歷的方式將其轉換成字串，使用括號表示子樹。需要省略不影響一對一映射關係的空括號，但若左子樹為空而右子樹存在，左子樹的空括號不能省略。

Example:

Input: root = [1,2,3,4] Output: “1(2(4))(3)”

Intuition#

前序遍歷加上括號表示子樹結構，關鍵是判斷何時需要保留空括號。

若左右子樹都為空，不需要括號
若左子樹為空但右子樹存在，左邊需要空括號 () 來保持結構明確
若左子樹存在但右子樹為空，右邊的括號可以省略

Approaches#

⭐ 1: Recursive DFS#

概念: 前序遍歷，根據左右子樹是否存在決定括號的添加
時間複雜度: O(n)，每個節點訪問一次
空間複雜度: O(h)，遞迴堆疊深度

class Solution {
    fun tree2str(root: TreeNode?): String {
        if (root == null) return ""
        val sb = StringBuilder()
        fun dfs(node: TreeNode?) {
            if (node == null) return
            sb.append(node.`val`)
            if (node.left != null || node.right != null) {
                sb.append("(")
                dfs(node.left)
                sb.append(")")
            }
            if (node.right != null) {
                sb.append("(")
                dfs(node.right)
                sb.append(")")
            }
        }
        dfs(root)
        return sb.toString()
    }
}

2: Iterative with Stack#

概念: 用 Stack 模擬前序遍歷，使用 Set 記錄已處理的節點來決定何時加右括號
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun tree2str(root: TreeNode?): String {
        if (root == null) return ""
        val sb = StringBuilder()
        val stack = ArrayDeque<TreeNode>()
        val visited = HashSet<TreeNode>()
        stack.addLast(root)
        while (stack.isNotEmpty()) {
            val node = stack.last()
            if (node in visited) {
                stack.removeLast()
                sb.append(")")
            } else {
                visited.add(node)
                sb.append("(${node.`val`}")
                if (node.left == null && node.right != null) {
                    sb.append("()")
                }
                node.right?.let { stack.addLast(it) }
                node.left?.let { stack.addLast(it) }
            }
        }
        // 移除最外層的括號
        return sb.substring(1, sb.length - 1)
    }
}

🔑 Takeaways#

Pattern: 樹的序列化 — 用括號表示子樹結構
關鍵技巧: 省略括號的規則：右子樹為空可省略，但左子樹為空且右子樹存在時必須保留空括號 ()