代码随想录算法训练营第16天 | 第六章 二叉树 part06

530.二叉搜索树的最小绝对差

需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接/文章讲解：link
视频讲解：link

/*** 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:int result =INT_MAX;TreeNode* pre;void traversal(TreeNode* cur){if (cur==nullptr)return;traversal(cur->left);if (pre!=nullptr)result=abs(cur->val-pre->val)>result?result:abs(cur->val-pre->val);pre=cur;traversal(cur->right);}int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

中序遍历能够按照递增顺序访问节点的值。因此，最小绝对差一定是相邻节点之间的差值，写的时候才注意到，完全没必要用abs函数求绝对值。

int getMinimumDifference(TreeNode* root) {stack<TreeNode*> stk;TreeNode* cur = root;TreeNode* pre = nullptr;int result = INT_MAX;while (!stk.empty() || cur != nullptr) {while (cur != nullptr) {stk.push(cur);cur = cur->left;}cur = stk.top();stk.pop();  if (pre != nullptr) {result = min(result, abs(cur->val - pre->val));}pre = cur;        cur = cur->right;}return result;
}

使用栈来实现中序遍历的迭代版本，从而避免栈溢出问题。同时避免代码中使用了全局变量 pre 和 result，这可以将它们作为函数参数传递=。

501.二叉搜索树中的众数

和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
如果不是二叉搜索树，我也想到的最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
可以先自己做做看，然后看视频讲解。

普通二叉树

这也是一个难题，如果树中有不止一个众数，可以按 任意顺序 返回。遍历 unordered_map，寻找频率最大的节点值。使用 keyVector.clear() 清空之前的众数，如果发现有更新的更大频率值，就将新的值加入 vector。如果遇到相同频率的值，则追加到 keyVector

link
视频讲解：link

/*** 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 searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历if (cur == NULL) return ;map[cur->val]++; // 统计元素频率searchBST(cur->left, map);searchBST(cur->right, map);return ;
}                  vector<int> findMode(TreeNode* root) {std::unordered_map<int, int> map;searchBST(root, map);int maxKey = map.begin()->second;  // 初始将第一个键作为最大值std::vector<int> keyVector; // 遍历unordered_mapfor (const auto& pair : map) {if (pair.second > maxKey) {maxKey = pair.second;     keyVector.clear();   keyVector.push_back(pair.first);  } else if (pair.second == maxKey) {keyVector.push_back(pair.first);}}return keyVector;}
};

使用 unordered_map<int, int> 来存储每个节点值以及它出现的次数。map[cur->val]++ 这一步递增节点值 val 的频率。

搜索二叉树

想到搜索二叉树，首先想到中序遍历，每一次 弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组）.频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。
count = 0;
maxCount = 0;
pre = NULL;
result.clear();//看了代码随想录的代码，确实不能忘了全局变量初始化，因为我们写的是子函数，得要被调用很多次。第一次被用完，再一次调用要记得初始化。

代码看着挺麻烦，实际上只要把思路给搞懂，仅仅是麻烦不复杂。中序遍历，判断最大清空或者导入数组，就这两部分。外加上全局变量的设定和初始化。

/*** 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;
int maxCount = 0; 
int count = 0; 
vector<int> result;
void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left); if (pre == NULL) { count = 1; } else if (pre->val == cur->val) { count++;} else { count = 1;}pre = cur; // 更新上一个节点if (count == maxCount) { // 如果和最大值相同，放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;  result.clear();     result.push_back(cur->val);}      searchBST(cur->right);      return;}vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = nullptr; // 记录前一个节点result.clear();searchBST(root);return result;}
};

236. 二叉树的最近公共祖先

本题其实是比较难的，可以先看视频讲解

link
视频讲解：link
先想下思路如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。

在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == q || root == p || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != NULL && right != NULL) return root;if (left == NULL && right != NULL) return right;else if (left != NULL && right == NULL) return left;else  { //  (left == NULL && right == NULL)return NULL;}}
};

这题很巧妙，如果当前节点是 p 或 q，或者当前节点为空（root == NULL），直接返回当前节点作为结果。当前节点如果是其中一个目标节点，说明找到了一个目标节点，此时可能是公共祖先。 递归地在左子树 root->left 和右子树 root->right 上分别查找目标节点 p 和 q，将结果分别存储在 left 和 right。就是一层层往下查。 如果发现左边找到了一个,右边找到了一个，那就返回当前结点。 如果发现都是在左边找到的如果 left != NULL && right != NULL，说明 p 和 q 分别在当前节点的左右子树中，所以当前节点 root 就是它们的最近公共祖先。 如果 left == NULL && right != NULL，说明 p 和 q 都在右子树中，返回 right 作为结果。 如果 left != NULL && right == NULL，说明 p 和 q 都在左子树中，返回 left 作为结果。 如果 left == NULL && right == NULL，说明在当前节点的子树中没有找到 p 或 q，返回 NULL。