今日算法: 二叉搜索树

思路二叉搜索树已经有序将树放进数组中然后进行比较class Solution { public: vectorint vec; void traversal(TreeNode*root) { if(rootnullptr) return; traversal(root-left); vec.push_back(root-val); traversal(root-right); } int getMinimumDifference(TreeNode* root) { //用一个vector存有序数组进行临近比较 traversal(root); if(vec.size()2) return 0; int result INT_MAX; for(int i1;ivec.size();i) { resultmin(result,vec[i]-vec[i-1]); } return result; } };思路在中序遍历时我们可以直接进行比较只不过需要记录前一个节点class Solution { public: int resultINT_MAX; TreeNode*preNULL; void traversal(TreeNode*root) { if(rootNULL) return; traversal(root-left);//左 if(pre!nullptr) { resultmin(result,root-val-pre-val);//中 } preroot; traversal(root-right); } int getMinimumDifference(TreeNode* root) { //用一个vector存有序数组进行临近比较 traversal(root); return result; } };使用迭代法:用栈进行记住前后的就行class Solution { public: int getMinimumDifference(TreeNode* root) { //使用栈进行遍历 stackTreeNode* st; TreeNode*curroot; TreeNode*prenullptr; int resultINT_MAX; while(cur!nullptr||!st.empty()) { if(cur!nullptr)//不为空入栈 { st.push(cur); curcur-left; } else//为空 { curst.top(); st.pop(); if(pre!nullptr) { resultmin(result,cur-val-pre-val); } precur; curcur-right; } } return result; } };