LeetCode#530
题目链接
题意的意思是给你一个二叉树，然后找到二叉树中所有节点里绝对值差最小的值，我用了一个比较笨的方法，将树遍历，然后排序，再遍历一遍数组即可，先附代码：
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
| class Solution {
public:
void dfs(TreeNode* node,vector<int>&ve){
if(node==nullptr)
return;
ve.push_back(node->val);
dfs(node->right,ve);
dfs(node->left,ve);
}
int getMinimumDifference(TreeNode* root) {
int ans = -1;
vector<int>ve;
dfs(root,ve);
if(ve.size() == 2)
return abs(ve[0]-ve[1]);
sort(ve.begin(),ve.end());
for(int i = 1; i < ve.size()-1 ;i++)
{
int cur = min(abs(ve[i]-ve[i-1]),abs(ve[i]-ve[i+1]));
if(ans == -1)
ans = cur;
else
ans = ans < cur ? ans: cur;
}
return ans;
}
};
|
看了一下题解，整体思路类似，但是题解用了更优的解法，首先是一个我没注意到的条件，二叉搜索树眼睛是个好东西，这样就保证了只要使用中序遍历，即可保证获得的数组是排好序的数组；然后就是我们可以一边遍历一边取最小的差值，这样就又节省了遍历数组的时间复杂度，和开辟新的数组的额外空间复杂度……
附代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
void dfs(TreeNode* root, int& pre, int& ans) {
if (root == nullptr) {
return;
}
dfs(root->left, pre, ans);
if (pre == -1) {
pre = root->val;
} else {
ans = min(ans, root->val - pre);
pre = root->val;
}
dfs(root->right, pre, ans);
}
int getMinimumDifference(TreeNode* root) {
int ans = INT_MAX, pre = -1;
dfs(root, pre, ans);
return ans;
}
};
|
