Giả sử chúng ta có một giá trị k và một cây tìm kiếm nhị phân, ở đây mỗi nút là một lá hoặc chứa 2 nút con. Chúng ta phải tìm nút chứa giá trị k và trả về giá trị của nút anh em của nó.
Vì vậy, nếu đầu vào giống như
k =4., thì đầu ra sẽ là 10.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dùng (). Điều này sẽ bắt nguồn từ gốc, k, ans
-
nếu bên trái của thư mục gốc không phải là null và bên phải của thư mục gốc không phải là giá trị rỗng, thì
-
trở lại
-
-
nếu k> giá trị của gốc thì
-
nếu giá trị của quyền gốc giống với k, thì
-
chèn giá trị của left of root vào cuối ans
-
trở lại
-
-
nếu không,
-
sử dụng (quyền gốc, k, ans)
-
-
-
nếu k
-
nếu giá trị của quyền gốc giống với k, thì
-
chèn giá trị của quyền gốc vào cuối ans
-
trở lại
-
-
nếu không,
-
use (bên trái của root, k, ans)
-
-
-
Từ phương thức chính, thực hiện như sau -
-
ans:=một danh sách mới
-
sử dụng (root, k, ans)
-
trả về ans [0]
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 util(root, k, ans): if root.left is None and root.right is None: return if k > root.val: if root.right.val == k: ans.append(root.left.val) return else: util(root.right, k, ans) if k < root.val: if root.left.val == k: ans.append(root.right.val) return else: util(root.left, k, ans) class Solution: def solve(self, root, k): ans = [] util(root, k, ans) return ans[0] root = TreeNode(6) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5) ob1 = Solution() print(ob1.solve(root, 4))
Đầu vào
root = TreeNode(6) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(3) root.left.right = TreeNode(5) 4
Đầu ra
10