非科班學習算法day19?| LeetCode530:二叉搜索樹的最小絕對差?，Leetcode501:二叉搜索樹的眾數 ，Leetcode236:二叉樹的最近公共祖先?

目錄

介紹

一、LeetCode題目

1.LeetCode530:二叉搜索樹的最小絕對差?

題目解析

?2.Leetcode501: 二叉搜索樹的眾數?

題目解析

3.Leetcode236:二叉樹的最近公共祖先

題目解析

?

總結

---

介紹

包含LC的兩道題目，還有相應概念的補充。

相關圖解和更多版本：

代碼隨想錄 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

---

一、LeetCode題目

1.LeetCode530:二叉搜索樹的最小絕對差?

題目鏈接：530. 二叉搜索樹的最小絕對差 - 力扣（LeetCode）

題目解析

? ? ? ?首先要知道，最小絕對差會出現在什么位置，因為限定了任意兩個數的差值，但根據二叉搜索樹的特點，如果用相隔遠的兩個數相減，差值一定大于相鄰兩數，所以問題退化到中序遍歷相鄰兩數計算最小差值。

? ? ? ? 可以采用設置臨時指針pre來一遍遍歷就完成。

? ? ? ? 或者直觀的方法，中序遍歷記錄元素信息，將得到的數組進行遍歷。

?c++代碼如下：

/*** 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:// 需要中序遍歷，最小差出現在前后兩個數中間，所以可以設置臨時指針// 創建臨時指針TreeNode* pre = nullptr;// 創建最大值int min_dif = INT_MAX;// 中序遍歷函數void dis(TreeNode* root) {if (!root)return;// 左dis(root->left);// 處理if (pre) {int cur_dif = abs(pre->val - root->val);min_dif = min(min_dif, cur_dif);}pre = root;dis(root->right);return;}int getMinimumDifference(TreeNode* root) {dis(root);return min_dif;}
};

比較直觀的c++代碼如下：

/*** 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:void dis(TreeNode* root, vector<int>& vec) {if (!root)return;dis(root->left, vec);vec.push_back(root->val);dis(root->right, vec);return;}int getMinimumDifference(TreeNode* root) {vector<int> result;dis(root, result);int min_num = INT_MAX;for (int i = 0; i < result.size() - 1; ++i) {min_num = min(min_num, result[i + 1] - result[i]);}return min_num;}
};

?2.Leetcode501: 二叉搜索樹的眾數?

題目鏈接：501. 二叉搜索樹中的眾數 - 力扣（LeetCode）

題目解析

? ? ? ?個人認為很喜歡的一道題目，我遵循的也是雙指針思想：中序遍歷，實時更新最大長度，然后將最大長度對應的結果放到返回數組中，但是遇到了問題：

? ? ? ? 1.最大初始長度設置為0，這樣一開始的根節點怎么處理，因為實際上最小的長度應該是1

? ? ? ? 2.在一次遍歷的過程中，如果發現最大值就記錄，其實不能保證這是全過程的最大長度（后面的可能會有更長的），那么彈出的條件怎么設置。
? ? ? ?

?C++代碼如下：?

/*** 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:// 設置前一指針TreeNode* pre = nullptr;// 設置最大長度int max_len = 0;// 設置當前長度int len = 0;vector<int> res;void dis(TreeNode* root) {if (!root)return;dis(root->left);if (!pre)len = 1;else if (pre->val == root->val) {len++;} elselen = 1;if (len == max_len) {res.push_back(root->val);}if (len > max_len) {max_len = len;res.clear();res.push_back(root->val);}pre = root;dis(root->right);return;}vector<int> findMode(TreeNode* root) {max_len = 0;len = 0;res.clear();pre = nullptr;dis(root);return res;}
};

關于這兩個問題：1.pre指針還指向空的時候就把指針設置為1，注意在長度沒有增加時候else情況，要把長度重置為1，這點很重要。其實我認為也可以直接初始化就設置為1；

2.沒有必要彈出，因為如果后面搜索到更長的長度，我們只需要清空當前結果就可以了，前面的結果都不是想要的。

??

3.Leetcode236:二叉樹的最近公共祖先

題目鏈接：236. 二叉樹的最近公共祖先 - 力扣（LeetCode）

題目解析

? ? ? ?一開始理解的很艱難，因為涉及到類似于從底部向上檢索的過程，這里面是一定有回溯。首先糾正一個問題，就是我在嘗試用bool的返回類型輔助函數，但是我寫的過程中發現我無法用這個函數來記錄或者說返回節點信息，除非是用pair來記錄存在信息和節點信息，那樣理解是相對好了，但是寫法上復雜度大大增加。

? ? ? ? 現在的寫法的關鍵就是，還是后序遍歷的模板，但是在回溯過程中（就是return！）當不存在我們需要檢索的值時候，返回空指針，這樣也可以幫助我們bool判斷！

? ? ? ? 標記一下，相關的有需要下向上搜索的題目，后期再比對總結：樹的最大深度/最小深度，樹的直徑，路徑總和問題

C++代碼如下：

/*** 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:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root)return NULL;if (root->val == p->val || root->val == q->val)return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left && right)return root;if (!left && right)return right;if (left && !right)return left;elsereturn NULL;}
};

注意點1：代碼雖然看起來簡單，但是這個中止條件之所以沒有放在后面是因為，遵循的邏輯是先向下搜索，搜索到需要值，返回這個節點信息到上一層，這樣就記錄了節點信息。

而后面的處理是針對于一層遞歸左右結束之后中節點的處理邏輯，兩者是不一樣的，不要混淆。

?

總結

補打卡第19天，堅持！！！