注意是?叉搜索樹，?叉搜索樹可是有序的。
遇到在?叉搜索樹上求什么最值啊，差值之類的，就把它想成在?個(gè)有序數(shù)組上求最值，求差值，這樣就簡單多了。

遞歸法1

最直觀的想法，就是把?叉搜索樹轉(zhuǎn)換成有序數(shù)組，然后遍歷?遍數(shù)組，就統(tǒng)計(jì)出來最?差值了。

class Solution { public:void traversal(TreeNode* root,vector<int>& vec){if(root==nullptr) return;traversal(root->left,vec);vec.push_back(root->val);// 將?叉搜索樹轉(zhuǎn)換為有序數(shù)組traversal(root->right,vec);}int getMinimumDifference(TreeNode* root) {vector<int> vec;vec.clear();traversal(root,vec);int result=INT_MAX;for(int ii=1;ii<vec.size();ii++){result=min(result,vec[ii]-vec[ii-1]);// 統(tǒng)計(jì)有序數(shù)組的最?差值}return result;} };

遞歸法2

class Solution{ private:TreeNode* pre=NULL;int result=INT_MAX; public:void traversal(TreeNode* root){if(root==nullptr) return;traversal(root->left);if(pre!=NULL) {result=min(result,root->val-pre->val);}pre=root;traversal(root->right);}int getMinimumDifference(TreeNode* root){traversal(root);return result;}};

迭代法

class Solution{ public:int getMinimumDifference(TreeNode* root){stack<TreeNode*> st;TreeNode* cur=root;TreeNode* pre=NULL;int result=INT_MAX;while(cur!=NULL||!st.empty()){if(cur!=NULL){ // 指針來訪問節(jié)點(diǎn)，訪問到最底層st.push(cur); // 將訪問的節(jié)點(diǎn)放進(jìn)棧cur=cur->left;//左}else{cur=st.top(); //中st.pop();if(pre!=NULL) result=min(result,cur->val-pre->val);pre=cur;cur=cur->right;//右}}return result;} };

總結(jié)

遇到在?叉搜索樹上求什么最值，求差值之類的，都要思考?下?叉搜索樹可是有序的，要利?好這?特點(diǎn)。
同時(shí)要學(xué)會在遞歸遍歷的過程中如何記錄前后兩個(gè)指針，這也是?個(gè)?技巧，學(xué)會了還是很受?的。

總結(jié)

以上是生活随笔為你收集整理的二叉搜索树的最小绝对差的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。