Kiểm tra cây tìm kiếm nhị phân (Validate Binary Search Tree)

Nguồn: LeetCode

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một cây nhị phân có $n$ nút. Một cây được gọi là BST hợp lệ khi đồng thời thỏa các điều kiện sau tại mọi nút có khóa $v$:

• mọi khóa trong cây con trái đều nhỏ hơn $v$;
• mọi khóa trong cây con phải đều lớn hơn $v$;
• bản thân hai cây con cũng phải thỏa cùng định nghĩa.

Các bất đẳng thức là nghiêm ngặt, vì vậy hai nút có cùng khóa không thể cùng xuất hiện trong một BST hợp lệ.

Hãy xác định cây đã cho có phải BST hợp lệ hay không.

Input

Dòng đầu chứa hai số nguyên $n$ và $r$, trong đó $r$ là chỉ số gốc.

Tiếp theo có $n$ dòng. Dòng thứ $i$ mô tả nút $i$ bằng ba giá trị key left right. left và right bằng $0$ nếu không có nút con tương ứng; nếu khác $0$ thì là chỉ số trong $[1,n]$.

Dữ liệu được bảo đảm mô tả đúng một cây nhị phân liên thông, không có chu trình, có gốc $r$.

Output

In YES nếu cây là BST hợp lệ; ngược lại in NO.

Subtask

Subtask 1 (20 điểm): $1\le n\le 20$.

Subtask 2 (30 điểm): $1\le n\le 500$.

Subtask 3 (50 điểm): $1\le n\le 10^4$.

Trong tất cả các subtask, $-2^{31}\le \text{key}\le 2^{31}-1$.

Ví dụ

Input

5 1
8 2 3
3 4 5
10 0 0
1 0 0
9 0 0

Output

NO

Giải thích

Nút có khóa $9$ nằm trong cây con trái của nút gốc có khóa $8$. Điều kiện của BST yêu cầu mọi khóa trong toàn bộ cây con trái phải nhỏ hơn $8$, nhưng $9>8$.

Do đó cây không hợp lệ và output là NO.