做百度网站每年的费用,建设金融行业网站,专门做创意桌椅的网站,工程建设合同范本第一题#xff1a;
原题链接#xff1a;530. 二叉搜索树的最小绝对差 - 力扣#xff08;LeetCode#xff09;
思路#xff1a;
使用中序遍历的方式#xff1a;左中右。
定义一个pre节点来存放当前节点的前一个节点。
在中序的时候处理递归逻辑#xff1a;
首先先向…第一题
原题链接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中
如果countmaxcount的值话则需要将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:vectorint findMode(TreeNode* root) {if(root nullptr) return {};dfs(root);return res;}
private:int count 0, maxcount 0; TreeNode* pre nullptr;vectorint 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;}
};
