LeetCode530 Minimum Absolute Difference in BST

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:

1
\
3
/
2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

思路

求节点为非负整数的二叉搜索树中,任意两个节点绝对差值的最小值。

根据二叉搜索树的性质,对其进行中序遍历即可得到一个有序(从小到大)的结果。由于结果是有序的,因此只需要考虑相邻两个元素之间的差值来获得最小值。

比如对如下的二叉搜索树进行中序遍历,得到 [3, 5, 7, 8, 10]

1
2
3
4
5
   5
/ \
3 8
/ \
7 10

然后答案即为相邻元素的最小差值,ans = min {5-3, 7-5, 8-7, 10-8} = 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int ans, pre;
public:
void inOrder(TreeNode* root) {
if (root == NULL) return ;
inOrder(root->left);
ans = min(ans, root->val - pre);
pre = root->val;
inOrder(root->right);
}
int getMinimumDifference(TreeNode* root) {
ans = INT_MAX;
pre = -0x3f3f3f3f; // 记录中序遍历时当前节点的前驱
inOrder(root);
return ans;
}
};
分享到 评论