ได้ต้นไม้ไบนารี สร้างสตริงจาก preorder traversal ใช้วงเล็บแทนโหนดลูก NULL แทนด้วย "()" ลบวงเล็บว่างที่ไม่ส่งผลต่อการแมปปิงหนึ่งต่อหนึ่ง
ตัวอย่าง
ต้นไม้: 5 (ซ้าย:6(ขวา:8), ขวา:7) → "5(6()(8))(7)"
ขั้นตอนการแก้ปัญหา (Recursive)
- ถ้าโหนดเป็น NULL → คืนสตริงว่าง
- ถ้าโหนดเป็นใบ (ไม่มีลูก) → คืนค่าโหนด
- สร้างสตริง:
val + (left) + (right) - ถ้ามีลูกซ้าย → ใส่
(left)มิฉะนั้น() - ถ้ามีลูกขวา → ใส่
(right)
การติดตั้งใน Python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def tree2str(self, root):
def dfs(node):
if not node:
return ""
if not node.left and not node.right:
return str(node.val)
left = dfs(node.left)
right = dfs(node.right)
if not node.right:
return f"{node.val}({left})"
return f"{node.val}({left})({right})"
return dfs(root)
# Helper สร้างต้นไม้จากรายการ level-order
def build_tree(vals):
if not vals: return None
root = TreeNode(vals[0])
queue = [root]
i = 1
while queue and i < len(vals):
node = queue.pop(0)
if vals[i] is not None:
node.left = TreeNode(vals[i])
queue.append(node.left)
i += 1
if i < len(vals) and vals[i] is not None:
node.right = TreeNode(vals[i])
queue.append(node.right)
i += 1
return root
ob = Solution()
root = build_tree([5,6,7,None,8])
print(ob.tree2str(root)) # 5(6()(8))(7)
อินพุต / เอาต์พุต
Input: [5,6,7,None,8] Output: 5(6()(8))(7)
