문제가 있는 이진 트리가 있다고 가정합니다. 노드의 오른쪽 자식 포인터 중 하나가 이진 트리의 같은 수준에 있는 다른 노드를 잘못 가리킵니다. 따라서 이 문제를 해결하려면 이 오류가 있는 노드를 찾아 잘못 가리키고 있는 노드를 제외한 해당 노드와 해당 노드의 자손을 삭제해야 합니다. 고정 바이너리 트리의 루트 노드를 반환합니다.
따라서 입력이 다음과 같으면
4와 6 사이에 잘못된 링크가 있음을 알 수 있습니다. 4의 오른쪽 자식 포인터는 6을 가리킵니다.
그러면 출력에서 수정된 트리의 중위 표현은 -2, 3, 5, 6, 7, 8,
가 됩니다.노드 4는 노드 6에 대한 잘못된 링크가 있으므로 삭제됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
q :=루트를 포함하는 새 데크
-
p :=새 지도
-
방문:=새로운 세트
-
q가 비어 있지 않은 동안 수행
-
cur :=q의 가장 왼쪽 요소 팝
-
cur가 방문된 경우
-
is_left :=p[p[cur, 0]]
-
grand_p :=p[p[cur, 0]]
-
is_left가 null이 아니면
-
grand_p의 왼쪽 :=null
-
-
그렇지 않으면
-
grand_p의 오른쪽 :=null
-
-
루트 반환
-
-
추가(cur) 방문
-
cur의 왼쪽이 null이 아니면
-
p[cur의 왼쪽] :=새로운 튜플 (cur, 1)
-
q 끝에 cur의 왼쪽 삽입
-
-
cur의 오른쪽이 null이 아니면
-
p[cur의 오른쪽] :=새로운 튜플 (cur, 0)
-
q 끝에 cur의 오른쪽 삽입
-
-
-
루트 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
import collections 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 print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) def solve(root): q = collections.deque([root]) p, visited = dict(), set() while q: cur = q.popleft() if cur in visited: grand_p, is_left = p[p[cur][0]] if is_left: grand_p.left = None else: grand_p.right = None return root visited.add(cur) if cur.left: p[cur.left] = (cur, 1) q.append(cur.left) if cur.right: p[cur.right] = (cur, 0) q.append(cur.right) return root root = make_tree([5, 3, 7, 2, 4, 6, 8]) link_from = search_node(root, 4) link_to = search_node(root, 6) link_from.right = link_to print_tree(solve(root))
입력
root = make_tree([5, 3, 7, 2, 4, 6, 8]) link_from = search_node(root, 4) link_to = search_node(root, 6) link_from.right = link_to
출력
2, 3, 5, 6, 7, 8,