目錄

• • 題目
  • 思路1：遞歸遍歷得到result數組(單調遞增)，然后對數組進行前后差分，取最小值
  • 思路2：不用數組，進行優化
  • 思路3、回顧迭代法求解

題目

給你一棵所有節點為非負值的二叉搜索樹，請你計算樹中任意兩節點的差的絕對值的最小值。

思路1：遞歸遍歷得到result數組(單調遞增)，然后對數組進行前后差分，取最小值

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:void traversal(TreeNode* cur , vector<int>& vec){if(cur == NULL) return;traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec);}int getMinimumDifference(TreeNode* root) {vector<int> result;traversal(root,result);//遞增序列，所以絕對值的最小值就在差分數組中int Minimum =INT_MAX;for(int i =1;i<result.size();i++){Minimum = min(result[i]-result[i-1],Minimum);}return Minimum;} };

不過這樣的效率感覺比較低。

思路2：不用數組，進行優化

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int Minimum =INT_MAX; TreeNode* pre =NULL; //用來記錄前一個結點void traversal(TreeNode* cur){if(cur == NULL) return;traversal(cur->left);if(pre != NULL ) Minimum = min(cur->val-pre->val,Minimum);pre = cur; //更新結點traversal(cur->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return Minimum;} };

思路3、回顧迭代法求解

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public: int getMinimumDifference(TreeNode* root) {stack<TreeNode*> st;int Minimum =INT_MAX; TreeNode* cur = root;TreeNode* pre = NULL; while(!st.empty() || cur!=NULL){if(cur!=NULL){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();if(pre != NULL ) Minimum = min(cur->val-pre->val,Minimum);pre = cur; //更新結點cur = cur->right;}} return Minimum;} };

總結

以上是生活随笔為你收集整理的LeetCode 530. 二叉搜索树的最小绝对差 思考分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。