Cho hai cây biểu thức (cho dưới dạng in-order). Kiểm tra xem chúng có cho cùng giá trị không. Trả về True/False.
Thuật toán
- DFS(node, dict):
- Nếu node lá (không có left, right): dict[val] += 1
- DFS(left), DFS(right)
- Chạy DFS trên cả hai root, so sánh hai dict tần suất
Code Python
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 = [temp]
while que:
temp = que.pop(0)
if not temp.left:
temp.left = TreeNode(data) if data is not None else TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data) if data is not None else 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))
Input
root1 = make_tree([1, '+', 2, '*', 3, '+', 4]); root2 = make_tree([2, '+', 1, '*', 4, '+', 3])
Output
True