두 개의 표현식 트리가 제공된다고 가정합니다. 두 개의 표현식 트리를 확인하고 표현식 트리가 유사한 값을 생성하는지 확인하는 프로그램을 작성해야 합니다. 두 개의 표현식 트리가 순서대로 제공되며 일치하면 True 값을 반환하고 그렇지 않으면 False 값을 반환합니다.
따라서 입력이 다음과 같으면
그러면 출력이 True가 됩니다.
두 표현식 트리는 동일한 값으로 평가됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
dfs() 함수를 정의합니다. 이것은 노드, dic
을 취합니다.-
노드가 비어 있으면
-
반환
-
-
노드의 왼쪽과 노드의 오른쪽이 비어 있지 않으면
-
dic[노드 값] :=dic[노드 값] + 1
-
-
dfs(노드 왼쪽, dic)
-
dfs(노드 오른쪽, dic)
-
-
dic1 :=정수 값을 포함하는 새 맵
-
dic2 :=정수 값을 포함하는 새 맵
-
dfs(루트1, 딕1)
-
dfs(루트2, 딕2)
-
dic1이 dic2와 같으면 True를 반환합니다.
예
import collectionsclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val =val self.left =left self.right =rightdef insert(temp,data):que =[ ] que.append(temp) while (len(que)):temp =que[0] que.pop(0) if (not temp.left):데이터가 None이 아닌 경우:temp.left =TreeNode(data) else :temp.left =TreeNode(0) break else:que.append(temp.left) if (not temp.right):데이터가 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 Treedef solve(root1, root2) ):dic1 =collections.defaultdict(int) dic2 =collections.defaultdict(int) def dfs(node, dic):노드가 아닌 경우:node.left가 아니고 node.right가 아닌 경우 반환:dic[node .val] +=1 dfs(node.left, dic) dfs(node.right, dic) dfs(root1, dic1) dfs(root2, dic2) return dic1 ==dic2root1 =make_tree([1, '+', 2 , '*', 3, '+', 4 ])root2 =make_tree([2, '+', 1, '*', 4, '+', 3])print(solve(root1, root2))입력
루트1 =make_tree([1, '+', 2, '*', 3, '+', 4 ])root2 =make_tree([2, '+', 1, '*', 4, '+ ', 3])출력
사실