本文共 1176 字,大约阅读时间需要 3 分钟。
class Solution { public: // void inOrderTrave(TreeNode* root){ // if(root == nullptr) return; // inOrderTrave(root->left); // //第一次不比较,只更新pre // if(pre != nullptr){ // res = min(root->val-pre->val,res); // } // pre = root; // inOrderTrave(root->right); // } int minDiffInBST(TreeNode* root) { //bst的最小差值肯定是中序遍历的两个连续的结点差 //维护一个全局的res和一个pre结点,当用当前结点-pre更新res,比完之后更新一个pre //inOrderTrave(root); //用stack来模拟中序 //中序左根右,一直往左 stacksta; while(!sta.empty() || root != nullptr){ while(root != nullptr){ sta.push(root); root = root->left; } root = sta.top(); sta.pop(); if(pre != nullptr){ res = min(root->val-pre->val,res); } pre = root; root = root->right; } return res; }private: int res = INT_MAX; TreeNode* pre = nullptr;};
转载地址:http://rajuk.baihongyu.com/