二叉搜索树的最小绝对差
提高的二叉搜索树,直接中序遍历就是从小到达的数组。做两个数值的差,找最小的
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pre_val = INT_MIN , diff_val = INT_MAX; void min_diff(TreeNode* cur) { if(cur==nullptr) return ; min_diff(cur->left); if(pre_val != -1 && ( cur->val - pre_val ) < diff_val) diff_val = cur->val - pre_val; pre_val = cur->val; min_diff(cur->right); } int getMinimumDifference(TreeNode* root) { if(root==nullptr) return 0; min_diff(root); return diff_val; } };
二刷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: double result = INT_MAX; TreeNode* pre = nullptr; void trak_back(TreeNode* cur) { if( cur == nullptr ) return; trak_back(cur->left); if(pre != nullptr && cur->val - pre->val < result ) result = cur->val - pre->val; pre = cur; trak_back(cur->right); } int getMinimumDifference(TreeNode* root) { if(root == nullptr) return 0; trak_back(root); return result; } };