이진 트리와 이진 트리의 리프에 있는 노드가 있다고 가정합니다. 이진 트리의 루트 노드를 리프 노드로 만들어야 합니다. 다음과 같은 방법으로 할 수 있습니다 -
-
노드에 왼쪽 자식이 있으면 오른쪽 자식이 됩니다.
-
노드의 부모는 왼쪽 자식이 됩니다. 이 과정에서 해당 노드에 대한 부모 노드의 링크는 null이 되므로 자식이 하나만 있게 됩니다.
트리의 노드 구조는 아래와 같습니다 -
TreeNode: data: <integer> left: <pointer of TreeNode> right: <pointer of TreeNode> parent: <pointer of TreeNode>
변환된 트리의 루트를 반환해야 합니다.
따라서 입력이 다음과 같으면
새 루트는 8입니다. 그러면 변환된 트리의 중위 표현은 -2, 3, 4, 5, 7, 6, 8,
가 됩니다.트리의 새 루트 노드는 8입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
helper() 함수를 정의합니다. 이것은 new_par
노드를 사용합니다.-
노드가 루트와 같으면
-
노드의 부모 :=new_par
-
노드의 왼쪽이 new_par과 같으면
-
노드 왼쪽 :=null
-
-
노드의 오른쪽이 new_par와 같으면
-
노드 오른쪽 :=null
-
-
루트 반환
-
-
노드의 왼쪽이 null이 아니면
-
노드 오른쪽 :=노드 왼쪽
-
-
노드의 부모 왼쪽이 노드와 같으면
-
노드의 부모 왼쪽 :=null
-
-
노드의 왼쪽 :=도우미(노드의 부모, 노드)
-
노드의 부모 :=new_par
-
반환 노드
-
-
리턴 헬퍼(리프, 널)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
import collections 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 print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) def solve(root, leaf): def helper(node, new_par): if node == root: node.parent = new_par if node.left == new_par: node.left = None if node.right == new_par: node.right = None return root if node.left: node.right = node.left if node.parent.left == node: node.parent.left = None node.left = helper(node.parent, node) node.parent = new_par return node return helper(leaf, None) root = make_tree([5, 3, 7, 2, 4, 6, 8]) root = solve(root, search_node(root, 8)) print_tree(root)
입력
root = make_tree([5, 3, 7, 2, 4, 6, 8]) root = solve(root, search_node(root, 8))
출력
2, 3, 4, 5, 7, 6, 8,