이진 트리와 두 개의 특정 노드 x와 y가 주어졌다고 가정합니다. 이진 트리에서 두 노드의 가장 낮은 공통 조상을 찾아야 합니다. 이진 트리에서 가장 낮은 공통 조상은 노드 x와 y가 모두 자손인 가장 낮은 노드입니다. 또한 특정 노드는 자신의 자손이 될 수도 있습니다. 노드를 찾아서 출력으로 반환해야 합니다.
따라서 입력이 다음과 같으면
x =2, y =4; 그러면 출력은 3이 됩니다.
노드 2와 4의 자손 노드는 3이므로 3이 반환됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dfs() 함수를 정의합니다. 노드가 필요합니다.
-
노드가 null과 유사하면
-
반환
-
-
노드가 목록 [x,y]에 있으면
-
왼쪽 :=dfs(노드의 왼쪽)
-
right :=dfs(노드의 오른쪽)
-
왼쪽 또는 오른쪽이 0이 아니면
-
as :=노드
-
반환 노드
-
-
-
왼쪽 :=dfs(노드의 왼쪽)
-
right :=dfs(노드의 오른쪽)
-
왼쪽과 오른쪽이 null이 아니면
-
as :=노드
-
반환 노드
-
-
왼쪽 또는 오른쪽으로 돌아가기
-
-
답변 :=dfs(루트)
-
반환
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data 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 search_node(root, element): if (root == None): return None if (root.data == element): return root res1 = search_node(root.left, element) if res1: return res1 res2 = search_node(root.right, element) return res2 def solve(root, x, y): def dfs(node): if not node: return if node in [x,y]: left = dfs(node.left) right = dfs(node.right) if left or right: ans = node return node left = dfs(node.left) right = dfs(node.right) if left and right: ans = node return node return left or right ans = dfs(root) return ans root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]) print(solve(root, search_node(root, 2), search_node(root, 4)).data)
입력
make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]), search_node(root, 2), search_node(root, 4)
출력
3