代码随想录训练营第十八天 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;}
};