530. 二叉搜索樹的最小絕對差
題目鏈接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
算法思想：
因?yàn)槭嵌嫠阉鳂洌虼瞬捎弥行虮闅v的話缆镣，是有序的。采用一個前指針指向前一個節(jié)點(diǎn)，和當(dāng)前節(jié)點(diǎn)進(jìn)行比較单默。
代碼：
class Solution {
public:
? ? TreeNode* pre=NULL;
? ? int min = INT_MAX;
? ? void getmindata(TreeNode* root)
? ? {
? ? ? ? if (root==NULL)
? ? ? ? ? ? return;
? ? ? ? getmindata(root->left);
? ? ? ? if(pre!=NULL&&abs(root->val-pre->val)<min)
? ? ? ? {
? ? ? ? ? ? min = abs(root->val-pre->val);
? ? ? ? }
? ? ? ? pre = root;
? ? ? ? getmindata(root->right);
? ? }
? ? int getMinimumDifference(TreeNode* root) {
? ? ? ? getmindata(root);
? ? ? ? return min;
? ? }
};
501. 二叉搜索樹中的眾數(shù)
題目鏈接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/
算法思想：
使用一個max_count記錄當(dāng)前位置的最大值魏身，count記錄當(dāng)前元素的最大值你雌。vec記錄當(dāng)前記錄的元素、
當(dāng)最大值更新的時候蕉世，vec清空，重新加入眾數(shù)對應(yīng)的元素婆硬，如果最大值和count相同狠轻，直接加入。
class Solution {
public:
? ? TreeNode* pre=NULL;
? ? int count = 0;
? ? int max_count = 0;
? ? vector<int> res;
? ? void inorder(TreeNode* root)
? ? {
? ? ? ? if(root==NULL)
? ? ? ? {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? inorder(root->left);
? ? ? ? if(pre==NULL) // 前一個節(jié)點(diǎn)為空
? ? ? ? {
? ? ? ? ? ? count = 1;
? ? ? ? }
? ? ? ? else if(pre->val == root->val)
? ? ? ? ? ? count++;
? ? ? ? else
? ? ? ? ? ? count = 1; //和前一個節(jié)點(diǎn)相同
? ? ? ? pre = root;
? ? ? ? if(count == max_count)
? ? ? ? {
? ? ? ? ? ? res.push_back(root->val);
? ? ? ? }
? ? ? ? if(max_count<count)
? ? ? ? {?
? ? ? ? ? ? res.clear();
? ? ? ? ? ? max_count = count;
? ? ? ? ? ? res.push_back(root->val);?
? ? ? ? }?
? ? ? ? inorder(root->right);
? ? }
? ? vector<int> findMode(TreeNode* root) {
? ? ? ? inorder(root);
? ? ? ? return res;
? ? }
};
236. 二叉樹的最近公共祖先
題目鏈接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
算法思想：
采用后序遍歷柿祈。終止條件：遇到p或者q就返回哈误。
如果左子樹和右子樹都找到了p或者q哩至，則root為最近的公共祖先。
class Solution {
public:
? ? TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
? ? ? ? if(root==NULL)
? ? ? ? ? ? return NULL;
? ? ? ? if(root==p ||root==q)
? ? ? ? ? ? return root;
? ? ? ? TreeNode* left = lowestCommonAncestor(root->left, p, q);
? ? ? ? TreeNode* right = lowestCommonAncestor(root->right, p, q);
? ? ? ? if(left&&right)
? ? ? ? ? ? return root;
? ? ? ? else if(left)
? ? ? ? ? ? return left;
? ? ? ? else
? ? ? ? ? ? return right;
? ? }
};
