LeetCode783. 二叉搜索树节点最小距离

题目

和LeetCode530没什么区别

 1 class Solution {
 2 public:
 3     vector<int>ans;
 4     int minDiffInBST(TreeNode* root) {
 5         int min = INT_MAX;dfs(root);
 6         for(int i = 0;i < ans.size()-1;i++){
 7             if(abs(ans[i] - ans[i+1]) < min)
 8                 min = abs(ans[i] - ans[i+1]);
 9         }
10         return min;
11     }
12     void dfs(TreeNode* root){
13         if(root!=NULL){
14             dfs(root->left);
15             ans.push_back(root->val);
16             dfs(root->right);
17         }
18     }
19 };

双指针定义pre指针指针前一个结点

 1 class Solution {
 2 public:
 3     TreeNode *pre;
 4     int ans = INT_MAX;
 5     int minDiffInBST(TreeNode* root) {    
 6         dfs(root);
 7         return ans;
 8     }
 9     void dfs(TreeNode* root){
10         if(root!=NULL){
11             dfs(root->left);
12             if(pre!=NULL) ans = min(ans,abs(pre->val - root->val));
13             pre = root;
14             dfs(root->right);
15         }
16     }
17 };