530.二叉搜索树的最小绝对差
- 题目链接：530.二叉搜索树的最小绝对差
- 思路：中序遍历二搜索叉树，遍历结果是一个升序数组，所以差值产生于遍历结果中任意两个相邻的两个数，故使用pre记录上一次遍历的值，然后和当前值相减得到差值，每次取最小差值即可
- 代码：
class Solution {
public:void dfs(TreeNode* root, int& pre, int& ans) {if (root == nullptr) {return;}dfs(root->left, pre, ans); // 先遍历左子树if (pre == -1) {pre = root->val; // 等于当前值} else {ans = min(ans, root->val - pre); // 取最小差值pre = root->val; // 记录当前遍历的节点值}dfs(root->right, pre, ans);}int getMinimumDifference(TreeNode* root) {int ans = INT_MAX, pre = -1; // pre = -1 取二叉树节点中没有的值dfs(root, pre, ans);return ans;}
};
501.二叉搜索树中的众数
- 题目链接：501.二叉搜索树中的众数
- 思路：中序遍历二叉搜索树，遍历结果是升序的，故相同的数一定是排列在一块儿的，所以遍历时记录上一次遍历节点的结果，和遍历节点的最大子树，每遍历一个节点更新一下
- 代码：
class Solution {
private:int max_cnt = 0; // 最大频次int cnt = 0; // 当前元素出现频次TreeNode* pre = nullptr; // 前驱节点vector<int> res; // 保存众数void dfs(TreeNode* root) // 中序遍历{if (root == nullptr) return;dfs(root->left);if (pre && pre->val == root->val)cnt++; // 与前驱相同，频次++ elsecnt = 1; // 是没前驱的首个节点，或非重复元素，频次初始化if (cnt == max_cnt) // 成为了众数之一 res.push_back(root->val);if (cnt > max_cnt) // 频次突破新高，成为众数，并且之前的众数无效了{res.clear();max_cnt = cnt;res.push_back(root->val);} pre = root; // 更新前驱dfs(root->right);}
public:vector<int> findMode(TreeNode* root) {dfs(root);return res;}
};
236. 二叉树的最近公共祖先
- 题目链接：236. 二叉树的最近公共祖先
- 思路：遍历二叉树，遍历左右子树，如果找到p或q，返回当前节点，如果没找到返回NULL，如果左右子树找到只找到一个，返回找到的节点，左右子树都找到，返回当前节点
- 代码：
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL || root == p || root == q) return root; //找到返回当前节点TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左子树查找p,qTreeNode* right = lowestCommonAncestor(root->right, p, q); // 右子树查找p,qif(left == NULL) return right; if(right == NULL) return left; // 只找到其中一个就返回另外一个return root; // 都找到返回当前节点}
};
