Chương trình tìm giá trị nút anh em của một nút trong cây nhị phân bằng Python

Giả sử chúng ta có một giá trị k và một cây tìm kiếm nhị phân, nơi mỗi nút hoặc là nút lá hoặc chứa đúng 2 nút con. Chúng ta cần tìm nút chứa giá trị k và trả về giá trị của nút anh em của nó.

Ví dụ, nếu đầu vào như sau:

k = 4, thì đầu ra sẽ là 10.

Quy trình giải quyết

1. Định nghĩa hàm util() nhận tham số root, k, ans.
2. Nếu cả nút con trái và phải của root đều không phải null, thì trả về.
3. Nếu k > root.val:
   • Nếu root.right.val == k, thêm root.left.val vào ans và trả về.
   • Ngược lại, gọi đệ quy util(root.right, k, ans).
4. Nếu k < root.val:
   • Nếu root.left.val == k, thêm root.right.val vào ans và trả về.
   • Ngược lại, gọi đệ quy util(root.left, k, ans).
5. Từ phương thức chính:
   • Khởi tạo ans là danh sách rỗng.
   • Gọi util(root, k, ans).
   • Trả về ans[0].

Ví dụ mã nguồn

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]

# Test
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))  # Output: 10

Đầ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