530. Minimum Absolute Difference in BST
Tags:
Easy
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 tìm hiệu tuyệt đối nhỏ nhất của hai node bất kỳ trong một BST. Một đặc điểm quan trọng của BST là nếu duyệt in-order ta sẽ nhận được dãy giá trị tăng dần. Vì vậy, hiệu nhỏ nhất chỉ có thể xuất hiện giữa hai node liền kề trong thứ tự này
Approach
prev prev , cập nhật kết quả nhỏ nhất minDiff prev thành giá trị node hiện tạiTime and space complexity
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 getMinimumDifference(root: TreeNode | null): number {
16 let min_diff = Infinity
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) {
22 min_diff = Math.min(min_diff, Math.abs(node.val - prev))
23 }
24 prev = node.val;
25 dfs(node.right)
26 }
27 dfs(root);
28 return min_diff
29};min_diff lưu hiệu nhỏ nhất tìm đượcprev lưu giá trị node trước đó trong thứ tự inorderinorder duyệt cây theo inorderprev , tính hiệu tuyệt đối với node hiện tại và cập nhật min_diff nếu cầnmin_diff sau khi duyệt xong cây