98. Validate Binary Search Tree
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra một binary tree có phải là cây nhị phân tìm kiếm (BST) hợp lệ hay không. Một cây BST hợp lệ phải thỏa mãn
Approach - Đệ quy kiểm tra giá trị trong khoảng (boundaries)
Không chỉ kiểm tra trực tiếp node.left < node.val < node.right, mà phải kiểm tra toàn bộ subtree có vi phạm không (VD node bên phải của node.left vẫn có thể lớn hơn root nếu không kiểm tra kỹ)
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function isValidBST(root: TreeNode | null): boolean {
16 function valid(node: TreeNode | null, left: number, right: number): boolean {
17 if (!node) return true;
18 if (node.val <= left || node.val >= right) return false
19 return valid(node.left, left, node.val) && valid(node.right, node.val, right);
20 }
21 return valid(root, -Infinity, Infinity)
22};valid nhận vào node hiện tại và khoảng giá trị [left, right] Approach - Duyệt kiểu inorder
prev ) và so sánh với node hiện tại, nếu node hiện tại không lớn hơn prev thì return về false Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function isValidBST(root: TreeNode | null): boolean {
16 let is_valid = true;
17 let prev: number | null = null;
18 function dfs(node: TreeNode | null): void {
19 if (!node) return;
20 dfs(node.left);
21 if (prev !== null && node.val <= prev) {
22 is_valid = false;
23 return;
24 }
25 prev = node.val
26 dfs(node.right)
27 }
28 dfs(root);
29 return is_valid
30};prev lưu giá trị node trước đó khi duyệt in-order.prev, gán isValid = false.isValid.