이진 트리와 두 개의 특정 노드 x와 y가 주어졌다고 가정합니다. 이진 트리에서 두 노드의 가장 낮은 공통 조상을 찾아야 합니다. 이진 트리에서 가장 낮은 공통 조상은 노드 x와 y가 모두 자손인 가장 낮은 노드입니다. 특정 노드는 자체의 하위 노드일 수도 있습니다. 노드를 찾아서 출력으로 반환해야 합니다.
트리의 노드 구조는 아래와 같습니다 -
TreeNode: data: <integer> left: <pointer of TreeNode> right: <pointer of TreeNode> parent: <pointer of TreeNode>
솔루션을 찾는 동안 부모 포인터를 활용해야 합니다.
따라서 입력이 다음과 같으면
x =3, y =7; 그러면 출력은 5가 됩니다.
3과 7은 모두 5의 자손이므로 답은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
path_p_r :=새 목록
-
x가 null이 아닌 동안 수행
-
path_p_r
끝에 x 삽입 -
x :=x의 부모
-
-
y가 null이 아닌 동안 수행
-
y가 path_p_r에 있으면
-
리턴 y
-
-
y :=y의 부모
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class TreeNode: def __init__(self, data, left = None, right = None, parent = None): self.data = data self.left = left self.right = right self.parent = parent 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, parent=temp) else: temp.left = TreeNode(0,parent=temp) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data,parent=temp) else: temp.right = TreeNode(0,parent=temp) 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(x, y): path_p_r = [] while x: path_p_r.append(x) x = x.parent while y: if y in path_p_r: return y y = y.parent root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]) print(solve(search_node(root, 3), search_node(root, 7)).data)
입력
[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7
출력
5