給定一棵二元樹，用前序遍歷的方式將其轉換成字串，使用括號表示子樹。需要省略不影響一對一映射關係的空括號，但若左子樹為空而右子樹存在，左子樹的空括號不能省略。
Example:
Input: root = [1,2,3,4] Output: “1(2(4))(3)“
Intuition
TIP
前序遍歷加上括號表示子樹結構，關鍵是判斷何時需要保留空括號。
- 若左右子樹都為空，不需要括號
- 若左子樹為空但右子樹存在，左邊需要空括號
()來保持結構明確 - 若左子樹存在但右子樹為空，右邊的括號可以省略
Approaches
⭐ 1. Recursive DFS — O(n) / O(h)
- Idea: 前序遍歷，根據左右子樹是否存在決定括號的添加
- Time:
O(n)，每個節點訪問一次 - Space:
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 — O(n) / O(n)
- Idea: 用 Stack 模擬前序遍歷，使用 Set 記錄已處理的節點來決定何時加右括號
- Time:
O(n) - Space:
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: 樹的序列化 — 用括號表示子樹結構
- Key trick: 省略括號的規則：右子樹為空可省略，但左子樹為空且右子樹存在時必須保留空括號
()