代码随想录训练营第十八天 530二叉搜索树的最小绝对差 501二叉搜索树中的众数 236二叉树的最近公共祖先
第一题：
原题链接：530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
思路：
使用中序遍历的方式：左中右。
定义一个pre节点来存放当前节点的前一个节点。
在中序的时候处理递归逻辑：
首先先向左遍历，
在中序的时候将当前节点和前一个节点的值相减取绝对值然后和res进行比较。然后pre更新为cur节点。
最后向右遍历。
代码如下：
/*** 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 getMinimumDifference(TreeNode* root) {if(root == nullptr) return 0;dfs(root);return res;}
private:int res = INT_MAX;TreeNode* pre = nullptr;void dfs(TreeNode* cur){if(cur == nullptr) return;dfs(cur -> left);if(pre != nullptr){res = min(res, abs(cur -> val - pre -> val));}pre = cur;dfs(cur -> right);return;}
};第二题：
原题链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）
思路：
使用中序遍历的方式，左中右。
定义一个pre节点来存放当前节点的前一个节点。
先向左进行遍历。
在中的时候处理逻辑：
如果pre为空的话证明当前节点是左下角的那个元素，count记录为1；
如果pre的值和cur的值相同，count++；
如果pre和cur不相等count也为1；
然后将pre更新为cur。
如果count的值和maxcount的值相等的话就将cur的值存放在res中，
如果count>maxcount的值话，则需要将res中的值全部都清空，再把cur的值存放到res中。maxcount更新为count的值。
最后向右遍历。
代码如下：
/*** 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:vector<int> findMode(TreeNode* root) {if(root == nullptr) return {};dfs(root);return res;}
private:int count = 0, maxcount = 0; TreeNode* pre = nullptr;vector<int> res;void dfs(TreeNode* cur){if(cur == nullptr) return;dfs(cur -> left);if(pre == nullptr) count = 1;else if(pre -> val == cur -> val){count++;}else{count = 1;}pre = cur;if(count == maxcount) res.push_back(cur -> val);if(count > maxcount){maxcount = count;res.clear();res.push_back(cur -> val);}dfs(cur -> right);return;}
};第三题：
原题链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
思路：
递归的终止条件：
如果root == null || root == p || root == q，都返回root；
本题使用后序遍历的方式，遍历到最后然后向上返回结果。
新建一个left节点来接收向左递归的结果，
新建一个right节点来接收向右递归的结果；
中：
如果left为空right不为空则返回right；
如果left不为空right为空则返回left；
如果left和right都不为空则返回root；
以上都不是则返回null；
代码如下：
/*** 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 == 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 == NULL && right != NULL) return right;if(left != NULL && right == NULL) return left;if(left != NULL && right != NULL) return root;return NULL;}
};