สมมติว่า เรามีต้นไม้นิพจน์สองต้น เราต้องเขียนโปรแกรมที่ตรวจสอบแผนผังนิพจน์ทั้งสองและกำหนดว่าแผนผังนิพจน์สร้างค่าที่คล้ายคลึงกันหรือไม่ ทรีนิพจน์สองรายการมีไว้ให้เราในลักษณะที่ไม่เป็นระเบียบ และเราส่งคืนค่า True หากตรงกัน มิฉะนั้นเราจะคืนค่าเป็นเท็จ
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็น True
ต้นไม้นิพจน์ทั้งสองจะประเมินเป็นค่าเดียวกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด dic
-
ถ้าโหนดว่างแล้ว
-
กลับ
-
-
หากด้านซ้ายของโหนดและด้านขวาของโหนดไม่ว่างเปล่า
-
dic[ค่าของโหนด] :=dic[ค่าของโหนด] + 1
-
-
dfs (ด้านซ้ายของโหนด dic)
-
dfs(ทางขวาของโหนด, dic)
-
-
dic1 :=แผนที่ใหม่ที่มีค่าจำนวนเต็ม
-
dic2 :=แผนที่ใหม่ที่มีค่าจำนวนเต็ม
-
dfs(root1, dic1)
-
dfs(root2, dic2)
-
คืนค่า True หาก dic1 เหมือนกับ dic2
ตัวอย่าง
import collections class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree def solve(root1, root2): dic1 = collections.defaultdict(int) dic2 = collections.defaultdict(int) def dfs(node, dic): if not node: return if not node.left and not node.right: dic[node.val] += 1 dfs(node.left, dic) dfs(node.right, dic) dfs(root1, dic1) dfs(root2, dic2) return dic1 == dic2 root1 = make_tree([1, '+', 2, '*', 3, '+', 4 ]) root2 = make_tree([2, '+', 1, '*', 4, '+', 3]) print(solve(root1, root2))
อินพุต
root1 = make_tree([1, '+', 2, '*', 3, '+', 4 ]) root2 = make_tree([2, '+', 1, '*', 4, '+', 3])
ผลลัพธ์
True
