LC530. 二叉搜索树的最小绝对差
这道题只要是在思考怎么不用另外写多一个函数进行递归,且不用多定义一个成员变量min_result,如下所示:
int min_result = INT_MAX;
TreeNode* prev = nullptr;
void getMinDiffLoop(TreeNode* root)
{
...
}
int getMinimumDifference(TreeNode* root)
{
getMinDiffLoop(root);
return min_result
}
而是用一个函数,由内部递归的返回值即可满足正确返回最终值:
对叶子节点来说,因为其左右孩子都为空,所以要让空节点返回INT_MAX才保证每层递归返回的都是以当前节点为root的子树的最小值。
TreeNode* prev = nullptr;
int getMinimumDifference(TreeNode* root)
{
int minDiff = INT_MAX;
if (root == nullptr)
{
return INT_MAX;
}
int leftDiff = getMinimumDifference(root->left);
if (prev != nullptr)
{
int temp = root->val - prev->val;
minDiff = temp < minDiff ? temp : minDiff;
}
prev = root;
int rightDiff = getMinimumDifference(root->right);
return min(min(leftDiff, minDiff), rightDiff);
}
LC501. 二叉搜索树中的众数
暴力解法思路:用一个unordered_map去记录各值出现的次数,并进行排序,输出次数最大的一个或多个值。(贴Carl哥代码)
void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
if (cur == NULL) return ;
map[cur->val]++; // 统计元素频率
searchBST(cur->left, map);
searchBST(cur->right, map);
return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> map; // key:元素,value:出现频率
vector<int> result;
if (root == NULL) return result;
searchBST(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
// 取最高的放到result数组中
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break;
}
return result;
}
如下思路:维护一个最大出现次数maxCount,中序遍历一次,prev保存前一个节点,出现重复值,Count+1记录,若遇到比当前maxCount更大的众数,则要清空结果集并更新maxCount。
int maxCount = 1;
int count = 1;
TreeNode* prev = nullptr;
void findModeLoop(TreeNode* root, vector<int>& result)
{
if (root == nullptr)
{
return;
}
findModeLoop(root->left, result);
if (prev != nullptr)
{
if (root->val == prev->val)
count++;
else
count = 1;
}
if (count > maxCount)
{
maxCount = count;
result.clear();
result.push_back(root->val);
}
else if (count == maxCount)
{
result.push_back(root->val);
}
prev = root;
findModeLoop(root->right, result);
}
vector<int> findMode(TreeNode* root)
{
vector<int> result;
findModeLoop(root, result);
return result;
}
LC236. 二叉树的最近公共祖先
想法是:后序遍历,如果找到了p或q中的某一个节点,必定要以某种形式记录并返回给其父节点,用个数组去记录的话,不好检验,所以还是选用了位运算更直观些
TreeNode* result = nullptr;
enum STAT
{
FIND_NONE = 0,
FIND_P = 1,
FIND_Q = 2,
FIND_ALL = 3
};
int AncestorLoop(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (root == nullptr || result != nullptr) //若result不为nullprt,说明已经找到了,不用再劳烦后面的验证了
{
return FIND_NONE;
}
int leftstat = AncestorLoop(root->left, p, q);
int rightstat = AncestorLoop(root->right, p, q);
int stat = 0;
if (root == p)
stat |= FIND_P;
if (root == q)
stat |= FIND_Q;
stat |= leftstat;
stat |= rightstat;
if (stat == FIND_ALL && result == nullptr) //result只会赋值一次
{
result = root;
}
return stat;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
AncestorLoop(root, p, q);
return result;
}
标签:TreeNode,int,nullptr,二叉,搜索,result,return,root,二叉树
From: https://www.cnblogs.com/Mingzijiang/p/17140411.html