530.Minimum Absolute Difference in BST
530.Minimum Absolute Difference in BST
难度:Easy
给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。
示例 :
1
输入:
2
3
1
4
\
5
3
6
/
7
2
8
9
输出:
10
1
Copied!
解释: 最小绝对差为1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 注意: 树中至少有2个节点。
递归判断,当前根节点的最小绝对差是与其左子树的最后最右节点的绝对差,和其与右子树的最后最左节点的绝对差的较小值。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
int getMinimumDifference(TreeNode* root) {
13
int m=std::numeric_limits<int>::max();
14
if(!root) return m;
15
int ld=m,rd=m;
16
if(root->left)
17
{
18
TreeNode* leftNode=root->left;
19
while(leftNode)
20
{
21
ld=root->val - leftNode->val;
22
leftNode=leftNode->right;
23
}
24
25
26
}
27
if(root->right)
28
{
29
TreeNode* rightNode=root->right;
30
while(rightNode)
31
{
32
rd=rightNode->val-root->val;
33
rightNode=rightNode->left;
34
}
35
36
37
}
38
39
40
// cout<<ld << " " <<rd << " "<< m<<endl;
41
if(root->left&& root->right)
42
{
43
m=min(ld,rd);
44
m=min(m,min(getMinimumDifference(root->left),getMinimumDifference(root->right)));
45
}
46
else if (root->left)
47
m=min(ld,getMinimumDifference(root->left));
48
else if(root->right) m=min(rd,getMinimumDifference(root->right));
49
else
50
return m;
51
// cout<<m<<endl;
52
return m;
53
}
54
};
Copied!
执行用时 : 40 ms, 在Minimum Absolute Difference in BST的C++提交中击败了86.97% 的用户 内存消耗 : 21.8 MB, 在Minimum Absolute Difference in BST的C++提交中击败了90.12% 的用户
Copy link