Giả sử chúng ta có một cây nhị phân và đó gần như là một cây tìm kiếm nhị phân. Chỉ có giá trị của hai nút được hoán đổi. Chúng tôi phải sửa nó và trả về cây tìm kiếm nhị phân.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- pres_node:=null, min_node:=null, max_node:=null
- found_one:=False
- đối với mỗi nút trong truyền tải cấp tốc của gốc, hãy thực hiện
- nếu pres_node không phải là null, thì
- nếu giá trị của nút
- nếu min_node là null hoặc giá trị của nút
- min_node:=node
- nếu min_node là null hoặc giá trị của nút
- nếu giá trị của nút
- nếu max_node là null hoặc giá trị của max_node
- max_node:=pres_node
- nếu pres_node không phải là null, thì
- nếu found_one là true, thì
- ra khỏi vòng lặp
- nếu không,
- found_one:=True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
root = TreeNode(3) root.left = TreeNode(6) root.right = TreeNode(8) root.right.left = TreeNode(2) root.right.right = TreeNode(9)
Đầu ra
2, 3, 6, 8, 9,