Cho một cây nhị phân tìm kiếm root và hai giá trị p, q. Hãy tìm giá trị của node là tổ tiên chung gần nhất (LCA) của hai node đó.
LCA của p và q được định nghĩa là node T sâu nhất trên cây sao cho cả p và q đều là con cháu của T (một node cũng được coi là con cháu của chính nó).
Ví dụ 1:
Input:
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
p = 2
q = 8
Output: 6
Giải thích: Node 6 là tổ tiên chung gần nhất của 2 và 8.Ví dụ 2:
Input:
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
p = 2
q = 4
Output: 2Định Dạng Đầu Vào (Input)
Dòng 1: Mảng cây BST root
Dòng 2: Số nguyên p
Dòng 3: Số nguyên q
Dòng 2: Số nguyên p
Dòng 3: Số nguyên q
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là giá trị của node LCA
Ràng Buộc (Constraints)
Tất cả giá trị trong cây là duy nhấtp != qp và q luôn tồn tại trong cây
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
2
8
Output:
6
Giải thích: Gốc 6 phân nhánh 2 và 8
Ví dụ 2:
Input:
[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
2
4
Output:
2
Giải thích: 2 là tổ tiên của 4
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Khai Thác Tính Chất BST O(h)
Bắt đầu từ gốc: Nếu cả p và q đều nhỏ hơn root -> đi sang cây con trái. Nếu cả hai đều lớn hơn root -> đi sang cây con phải. Ngược lại -> root chính là điểm phân nhánh (LCA).
Dữ liệu đầu vào (Input):
[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
2
8
Kết quả kỳ vọng (Expected Output):
6
Dữ liệu đầu vào (Input):
[6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
2
4
Kết quả kỳ vọng (Expected Output):
2
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
