이진 트리가 있고 거의 이진 검색 트리라고 가정합니다. 두 노드의 값만 교환됩니다. 이를 수정하고 이진 검색 트리를 반환해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- prev_node :=null, min_node :=null, max_node :=null
- found_one :=거짓
- 루트의 중위 순회에서 각 노드에 대해 다음을 수행합니다.
- prev_node가 null이 아니면
- 노드 값
- min_node가 null이거나 node의 값
- 최소 노드 :=노드
- min_node가 null이거나 node의 값
- 노드 값
- max_node가 null이거나 max_node의 값
- 최대 노드 :=이전 노드
- prev_node가 null이 아니면
- found_one이 참이면
- 루프에서 나오다
- 그렇지 않으면
- found_one :=사실
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right def print_tree(root): if root is not None: print_tree(root.left) print(root.val, end = ', ') print_tree(root.right) def __iter__(self): if self.left: for node in self.left: yield node yield self if self.right: for node in self.right: yield node setattr(TreeNode, "__iter__", __iter__) class Solution: def solve(self, root): prev_node = None min_node = None max_node = None found_one = False for node in root: if prev_node: if node.val < prev_node.val: if min_node is None or node.val < min_node.val: min_node = node if max_node is None or max_node.val < prev_node.val: max_node = prev_node if found_one: break else: found_one = True prev_node = node min_node.val, max_node.val = max_node.val, min_node.val return root ob = Solution() root = TreeNode(3) root.left = TreeNode(6) root.right = TreeNode(8) root.right.left = TreeNode(2) root.right.right = TreeNode(9) print_tree(ob.solve(root))
입력
root = TreeNode(3) root.left = TreeNode(6) root.right = TreeNode(8) root.right.left = TreeNode(2) root.right.right = TreeNode(9)
출력
2, 3, 6, 8, 9,