交友软件网站建设,网站备案相关手续费,网站邮件模板,如何推广我的网站530. 二叉搜索树的最小绝对差
1. LeetCode链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法 中序遍历#xff0c;记录前一个指针#xff0c;并记录前一个指针和当前指针的绝对差值。递归。
class Solution {
public:Tre…530. 二叉搜索树的最小绝对差
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法 中序遍历记录前一个指针并记录前一个指针和当前指针的绝对差值。递归。
class Solution {
public:TreeNode* pre NULL;int min INT_MAX;void order(TreeNode* root) {if (root NULL) return;order(root-left);if (pre ! NULL root-val - pre-val min) {min root-val - pre-val;}pre root;order(root-right);}int getMinimumDifference(TreeNode* root) {order(root);return min;}
};
统一迭代
class Solution {
public:int getMinimumDifference(TreeNode* root) {TreeNode* pre NULL;int result INT_MAX;stackTreeNode* st;st.push(root);while (!st.empty()) {TreeNode* cur st.top();if (cur ! NULL) {st.pop();if (cur-right ! NULL) st.push(cur-right);st.push(cur);st.push(NULL);if (cur-left ! NULL) st.push(cur-left);} else {st.pop();if (pre ! NULL (st.top()-val - pre-val) result) result st.top()-val - pre-val;pre st.top();st.pop();}}return result;}
};
501. 二叉搜索树中的众数
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
中序遍历记录指针、最大出现频率、当前数字累计个数、最终result。
class Solution {
public:TreeNode* pre NULL;int max 1;int count 1;vectorint result;void order(TreeNode* root) {if (root NULL) return;order(root-left);if (pre ! NULL root-val pre-val) count;if (pre ! NULL root-val ! pre-val) count 1;pre root;if (count max) {result.erase(result.begin(), result.end());result.push_back(pre-val);max count;} else if (count max) result.push_back(pre-val);order(root-right);}vectorint findMode(TreeNode* root) {order(root);return result;}
};
236. 二叉树的最近公共祖先
1. LeetCode链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 题目描述 3. 解法
自己想到的笨办法自顶向下找每次都要遍历一遍当前节点之下的节点。很耗时。
class Solution {
public:TreeNode* result;bool exist(TreeNode* root, TreeNode* p) {if (root NULL) return false;if (root p) return true;bool left exist(root-left, p);bool right exist(root-right, p);return left || right;}void order(TreeNode* root, TreeNode* p, TreeNode* q) {if (root NULL) return;if (exist(root, p) exist(root, q)) result root;if (root p || root q) return;order(root-left, p, q);order(root-right, p, q);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {order(root, p, q);return result;}
};
自底向上递归。就是找到p、q节点。如果恰好左右节点分别在某节点的左右子树上直接返回这个节点即为公共节点。
从下往上遍历就用后序遍历先判断完左右子树然后根据结果判断当前节点。
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root p || root q || 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 left;else if (left NULL right ! NULL) return right;else return NULL;}
};
