题目简介：
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：
1
\
3
/
2
输出：
1
解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
|
提示：
思路：
由于是二叉搜索树，所以其中序遍历必是一个升序序列。
所以我们定义一个pre来保存root的中序遍历前驱结点，在遍历过程中依次相减，并保存最小值，最后返回即可。
代码如下：
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
public:
int res = INT_MAX;
void dfs(TreeNode* root, int& pre){
if(!root)
return;
dfs(root -> left, pre);
if(pre == -1){
pre = root -> val;
}
else{
res = min(res, root -> val - pre);
pre = root -> val;
}
dfs(root -> right, pre);
}
int getMinimumDifference(TreeNode* root) {
int pre = -1;
dfs(root, pre);
return res;
}
};
|
