做网站卖什么/视频推广平台
目录
一、Leetcode 题目
1. 左叶子之和
(1)迭代法
(2)递归法
2. 找树左下角的值
(1)广度优先算法
(2)递归法
3. 路径总和
(1)递归法
(2)迭代法
4. 从中序与后序遍历序列构造二叉树
5. 从前序与中序遍历序列构造二叉树
6. 最大二叉树
7. 合并二叉树
(1)递归法
(2)迭代法
8. 二叉搜索树中的搜索
(1)递归法
(2)迭代法
9. 验证二叉搜索树
(1)递归法
(2)迭代法
10. 二叉搜索树的最小绝对差
11. 二叉搜索树中的众数
(1)递归法
(2)迭代法
一、Leetcode 题目
1. 左叶子之和
404. 左叶子之和 - 力扣(LeetCode)https://leetcode.cn/problems/sum-of-left-leaves/description/
给定二叉树的根节点
root
,返回所有左叶子之和。
示例 1:
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24示例 2:
输入: root = [1]
输出: 0
思路:
判断当前节点是不是左叶子是无法判断的,必须要通过节点的父节点来判断其左孩子是不是左叶子。
(1)迭代法
/*** 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 sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;if (root == NULL) return 0;st.push(root);int result = 0;while (!st.empty()) {TreeNode* node = st.top();st.pop();if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {result += node->left->val;}if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;}
};
(2)递归法
/*** 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 sumOfLeftLeaves(TreeNode* root) {// 递归法if (root == nullptr) return 0;if (!root->left && !root->right) return 0;int leftNum = sumOfLeftLeaves(root->left);if (root->left && !root->left->left && !root->left->right) {leftNum += root->left->val;}int rightNum = sumOfLeftLeaves(root->right);return leftNum + rightNum;}
};
2. 找树左下角的值
513. 找树左下角的值 - 力扣(LeetCode)https://leetcode.cn/problems/find-bottom-left-tree-value/submissions/567011451/
给定一个二叉树的 根节点
root
,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
(1)广度优先算法
/*** 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 findBottomLeftValue(TreeNode* root) {// 层序遍历queue<TreeNode*> record;int result = 0;if (root != nullptr) {record.push(root);result = root->val;}while (!record.empty()) {int size = record.size();for (int i = 0; i < size; i++) {TreeNode* node = record.front(); record.pop();if (i == 0) result = node->val;if (node->left) record.push(node->left);if (node->right) record.push(node->right);}}return result;}
};
(2)递归法
/*** 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 result;int maxdepth = INT_MIN;void traversal(TreeNode* node, int depth) {if (node == nullptr) return;if (!node->left && !node->right && depth > maxdepth) {maxdepth = depth;result = node->val;return;}traversal(node->left, depth + 1);traversal(node->right, depth + 1);}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};
3. 路径总和
112. 路径总和 - 力扣(LeetCode)https://leetcode.cn/problems/path-sum/description/
给你二叉树的根节点
root
和一个表示目标和的整数targetSum
。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和targetSum
。如果存在,返回true
;否则,返回false
。叶子节点 是指没有子节点的节点。
示例 1:
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
示例 2:
输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3:
输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。
思路:
递归:可以用递减,让计数器 count 初始为目标和,然后每次减去遍历路径节点上的数值。如果最后 count == 0,同时到了叶子节点的话,说明找到了目标和。如果遍历到了叶子节点,count 不为 0,就是没找到。(代码中包含着回溯)
迭代:栈里一个元素不仅要记录该节点指针,还要记录从头结点到该节点的路径数值总和。c++就用pair结构来存放这个栈里的元素。
定义为:
pair<TreeNode*, int>
pair<节点指针,路径数值> 这个为栈里的一个元素。
(1)递归法
/*** 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:bool PathSum(TreeNode* node, int targetSum) {if (node == nullptr) return false;if (!node->left && !node->right && targetSum == node->val) return true;bool leftTree = PathSum(node->left, targetSum - node->val);bool rightTree = PathSum(node->right, targetSum - node->val);return leftTree || rightTree;}bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;return PathSum(root, targetSum);}
};
(2)迭代法
/*** 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:bool hasPathSum(TreeNode* root, int targetSum) {// 遍历法stack<pair<TreeNode*, int>> record;if (root == nullptr) return false;record.push(pair<TreeNode*, int>(root, root->val));while (!record.empty()) {pair<TreeNode*, int> node = record.top();record.pop();if (!node.first->left && !node.first->right && node.second == targetSum) return true;if (node.first->right) {record.push(pair<TreeNode*, int>(node.first->right,node.second + node.first->right->val));}if (node.first->left) {record.push(pair<TreeNode*, int>(node.first->left,node.second + node.first->left->val));}}return false;}
};
4. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
给定两个整数数组
inorder
和postorder
,其中inorder
是二叉树的中序遍历,postorder
是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]
思路:
递归:
第一步:如果数组大小为零的话,说明是空节点了。
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)
第五步:切割后序数组,切成后序左数组和后序右数组
第六步:递归处理左区间和右区间
/*** 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:TreeNode* bTree(vector<int>& inorder, int inorderbegin, int inorderend,vector<int>& postorder, int postorderbegin, int postorderend) {if (postorderbegin == postorderend) return nullptr;// 获取根元素int mid = postorder[postorderend - 1];TreeNode* root = new TreeNode(mid);if (postorderend - postorderbegin == 1) return root;// 找到中序遍历中的根元素int inorderIndex;for (inorderIndex = inorderbegin; inorderIndex < inorderend; inorderIndex++) {if (mid == inorder[inorderIndex]) break;}// 中序遍历更新索引 [)int inorderbeginleft = inorderbegin;int inorderendleft = inorderIndex;int inorderbeginright = inorderIndex + 1;int inorderendright = inorderend;// 后序遍历更新索引 [)int postorderbeginleft = postorderbegin;int postorderendleft = postorderbeginleft + (inorderIndex - inorderbegin);int postorderbeginright = postorderendleft;int postorderendright = postorderend - 1;// for (int i = inorderbeginleft; i < inorderendleft; i++) {// cout << inorder[i] << " ";// }// cout << endl;// for (int i = inorderbeginright; i < inorderendright; i++) {// cout << inorder[i] << " ";// }// cout << endl;// for (int i = postorderbeginleft; i < postorderendleft; i++) {// cout << postorder[i] << " ";// // cout << i << " ";// }// cout << endl;// for (int i = postorderbeginright; i < postorderendright; i++) {// cout << postorder[i] << " ";// // cout << i << " ";// }// cout << endl;root->left = bTree(inorder, inorderbeginleft, inorderendleft,postorder, postorderbeginleft, postorderendleft);root->right = bTree(inorder, inorderbeginright, inorderendright,postorder, postorderbeginright, postorderendright);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (!inorder.size() || !postorder.size()) return nullptr;return bTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());}
};
5. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
给定两个整数数组
preorder
和inorder
,其中preorder
是二叉树的先序遍历,inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
/*** 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:TreeNode* bTree(vector<int>& preorder, int preorderbegin, int preorderend,vector<int>& inorder, int inorderbegin, int inorderend) {if (preorderbegin == preorderend) return nullptr;// 获取顶点节点int mid = preorder[preorderbegin];TreeNode* root = new TreeNode(mid);// 中序中遍历找到节点索引 [inorderbegin, inorderend)int inorderIndex;for (inorderIndex = inorderbegin; inorderIndex < inorderend; inorderIndex++) {if (mid == inorder[inorderIndex]) break;}// 更新前序遍历的索引 [preorderbegin, preorderend)int preorderbeginleft = preorderbegin + 1; int preorderendleft = preorderbegin + (inorderIndex - inorderbegin) + 1;int preorderbeginright = preorderendleft;int preorderendright = preorderend;// 更新中序遍历的索引 [inorderbegin, inorderend)int inorderbeginleft = inorderbegin;int inorderendleft = inorderIndex;int inorderbeginright = inorderIndex + 1;int inorderendright = inorderend;// for (int i = preorderbeginleft; i < preorderendleft; i++) {// cout << preorder[i] << " ";// }// cout << endl;// for (int i = preorderbeginright; i < preorderendright; i++) {// cout << preorder[i] << " ";// }// cout << endl;// for (int i = inorderbeginleft; i < inorderendleft; i++) {// cout << inorder[i] << " ";// }// cout << endl;// for (int i = inorderbeginright; i < inorderendright; i++) {// cout << inorder[i] << " ";// }// cout << endl;root->left = bTree(preorder, preorderbeginleft, preorderendleft,inorder, inorderbeginleft, inorderendleft);root->right = bTree(preorder, preorderbeginright, preorderendright,inorder, inorderbeginright, inorderendright);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (!preorder.size() || !inorder.size()) return nullptr;return bTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());}
};
6. 最大二叉树
654. 最大二叉树 - 力扣(LeetCode)https://leetcode.cn/problems/maximum-binary-tree/description/
给定一个不重复的整数数组
nums
。 最大二叉树 可以用下面的算法从nums
递归地构建:
- 创建一个根节点,其值为
nums
中的最大值。- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回
nums
构建的 最大二叉树 。
示例 1:
输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。- 空数组,无子节点。- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。- 空数组,无子节点。- 只有一个元素,所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。- 只有一个元素,所以子节点是一个值为 0 的节点。- 空数组,无子节点。
示例 2:
输入:nums = [3,2,1]
输出:[3,null,2,null,1]
/*** 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:TreeNode* buildTree(vector<int>& nums, int beginIndex, int endIndex) {if (beginIndex == endIndex) return nullptr;// 获取中心元素int midIndex = beginIndex;for (int i = beginIndex; i < endIndex; i++) {midIndex = nums[i] > nums[midIndex] ? i : midIndex;}// cout << midIndex << endl;TreeNode* root = new TreeNode(nums[midIndex]);// 重定义左右节点int leftbeginIndex = beginIndex;int leftendIndex = midIndex;int rightbeginIndex = midIndex + 1;int rightendIndex = endIndex;// for (int i = leftbeginIndex; i < leftendIndex; i++) {// cout << nums[i] << " ";// }// cout << endl;// for (int i = rightbeginIndex; i < rightendIndex; i++) {// cout << nums[i] << " ";// }// cout << endl;root->left = buildTree(nums, leftbeginIndex, leftendIndex);root->right = buildTree(nums, rightbeginIndex, rightendIndex);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if (nums.size() == 0) return nullptr;return buildTree(nums, 0, nums.size());}
};
7. 合并二叉树
617. 合并二叉树 - 力扣(LeetCode)https://leetcode.cn/problems/merge-two-binary-trees/description/
给你两棵二叉树:
root1
和root2
。想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]示例 2:
输入:root1 = [1], root2 = [1,2]
输出:[2,2]
思路:
递归:因为是传入了两个树,那么就有两个树遍历的节点root1 和 root2,如果root1 == NULL 了,两个树合并就应该是 root2 了(如果root2也为NULL也无所谓,合并之后就是NULL)。反过来如果root2 == NULL,那么两个数合并就是root1(如果root1也为NULL也无所谓,合并之后就是NULL)。
(1)递归法
/*** 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:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {// 递归if (root1 == nullptr) return root2;if (root2 == nullptr) return root1;TreeNode* root = new TreeNode(0);root->val = root1->val + root2->val;root->left = mergeTrees(root1->left, root2->left);root->right = mergeTrees(root1->right, root2->right);return root;}
};
(2)迭代法
/*** 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:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2;if (t2 == NULL) return t1;queue<TreeNode*> que; // 用于处理两棵树节点都有数的时候que.push(t1);que.push(t2);while(!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front(); que.pop();// 此时两个节点一定不为空,val相加node1->val += node2->val;// 如果两棵树左节点都不为空,加入队列if (node1->left != NULL && node2->left != NULL) {que.push(node1->left);que.push(node2->left);}// 如果两棵树右节点都不为空,加入队列if (node1->right != NULL && node2->right != NULL) {que.push(node1->right);que.push(node2->right);}// 当t1的左节点 为空 t2左节点不为空,就赋值过去if (node1->left == NULL && node2->left != NULL) {node1->left = node2->left;}// 当t1的右节点 为空 t2右节点不为空,就赋值过去if (node1->right == NULL && node2->right != NULL) {node1->right = node2->right;}}return t1;}
};
8. 二叉搜索树中的搜索
700. 二叉搜索树中的搜索 - 力扣(LeetCode)https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
给定二叉搜索树(BST)的根节点
root
和一个整数值val
。你需要在 BST 中找到节点值等于
val
的节点。 返回以该节点为根的子树。 如果节点不存在,则返回null
。
示例 1:
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5
输出:[]
(1)递归法
/*** 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:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;TreeNode* result = NULL;if (root->val > val) result = searchBST(root->left, val);if (root->val < val) result = searchBST(root->right, val);return result;}
};
(2)迭代法
/*** 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:TreeNode* searchBST(TreeNode* root, int val) {while (root != nullptr) {if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return nullptr;}
};
9. 验证二叉搜索树
98. 验证二叉搜索树 - 力扣(LeetCode)https://leetcode.cn/problems/validate-binary-search-tree/description/
给你一个二叉树的根节点
root
,判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
思路:
① 陷阱 1:
不能单纯的比较左节点小于中间节点,右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点,右子树所有节点大于中间节点。
② 陷阱 2:
样例中最小节点 可能是int的最小值,如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为 longlong 的最小值。
(1)递归法
/*** 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 {
private:vector<int> vec; // 保存到数组中再进行比较void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);}public:bool isValidBST(TreeNode* root) {vec.clear(); // 不加这句在leetcode上也可以过,但最好加上traversal(root);for (int i = 1; i < vec.size(); i++) {// 小于等于,搜索树里不能有相同元素if (vec[i] <= vec[i - 1]) return false;}return true;}
};// 方法二:记录递归的上个节点
class Solution {
public:TreeNode* pre = nullptr; // 中序遍历,记录前一个节点,只要出现正在遍历的值小于上个节点的值,就返回 falsebool isValidBST(TreeNode* root) {if (root == nullptr) return true;bool leftTree = isValidBST(root->left);if (pre && root->val <= pre->val) return false;else pre = root;bool rightTree = isValidBST(root->right);return leftTree && rightTree;}
};
(2)迭代法
/*** 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:bool isValidBST(TreeNode* root) {stack<TreeNode*> record;if (root != nullptr) record.push(root);TreeNode* cur = nullptr;while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {if (node->right) record.push(node->right);record.push(node);record.push(nullptr);if (node->left) record.push(node->left);}else {node = record.top();record.pop();if (cur && node->val <= cur->val) return false;cur = node; }}return true;}
};
10. 二叉搜索树的最小绝对差
530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
给你一个二叉搜索树的根节点
root
,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
/*** 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) {stack<TreeNode*> record;if (root != nullptr) record.push(root);TreeNode* cur = nullptr;int result = INT_MAX;while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {if (node->right) record.push(node->right);record.push(node);record.push(nullptr);if (node->left) record.push(node->left);}else {node = record.top();record.pop();if (cur) result = min(result, (node->val - cur->val));cur = node;}}return result;}
};
11. 二叉搜索树中的众数
501. 二叉搜索树中的众数 - 力扣(LeetCode)https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
给你一个含重复值的二叉搜索树(BST)的根节点
root
,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2]
输出:[2]示例 2:
输入:root = [0]
输出:[0]
思路 1:
这个树都遍历了,用map统计频率。想直接对 map 中的 value 排序,还真做不到,C++中如果使用 std::map 或者 std::multimap 可以对 key 排序,但不能对value排序。所以要把map转化数组即 vector,再进行排序,当然vector里面放的也是
pair<int, int>
类型的数据,第一个int为元素,第二个int为出现频率。数组 vector 中已经是存放着按照频率排好序的pair,那么把前面高频的元素取出来就可以了。
思路 2:
只需要遍历一次就可以找到所有的众数。频率count 大于 maxCount的时候,不仅要更新 maxCount(要把这个元素加入到结果集中),而且要清空结果集(以下代码为result数组),因为结果集之前的元素都失效了。
(1)递归法
/*** 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:void searchBST(unordered_map<int, int>& map, TreeNode* root) {if (root == nullptr) return;map[root->val]++;searchBST(map, root->left);searchBST(map, root->right);return;}bool static cmp(const pair<int, int> x, const pair<int, int> y) {return x.second > y.second;}vector<int> findMode(TreeNode* root) {// C++中如果使用std::map或者std::multimap可以对key排序,但不能对value排序// 设置大根堆unordered_map<int, int> map;vector<int> result;if (root == nullptr) return result;searchBST(map, root);// 放到 vector 中进行排序vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp);result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {if (vec[i].second == vec[i - 1].second) result.push_back(vec[i].first);else break;}return result;}
};
(2)迭代法
/*** 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:bool static cmp(const pair<int, int> x, const pair<int, int> y) {return x.second > y.second;}vector<int> findMode(TreeNode* root) {// 设置大根堆unordered_map<int, int> map;stack<TreeNode*> record;vector<int> result;if (root == nullptr) return result;record.push(root);while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {if (node->right) record.push(node->right);if (node->left) record.push(node->left);record.push(node);record.push(nullptr);}else {node = record.top();record.pop();map[node->val]++;}}// 放到 vector 中进行排序vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp);result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {if (vec[i].second == vec[i - 1].second) result.push_back(vec[i].first);else break;}return result;}
};// 方法二:(一次遍历)
class Solution {
public:vector<int> findMode(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;int maxCount = 0; // 最大频率int count = 0; // 统计频率vector<int> result;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left; // 左} else {cur = st.top();st.pop(); // 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count; // 更新最大频率result.clear(); // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}pre = cur;cur = cur->right; // 右}}return result;}
};
相关文章:

【算法篇】二叉树类(2)(笔记)
目录 一、Leetcode 题目 1. 左叶子之和 (1)迭代法 (2)递归法 2. 找树左下角的值 (1)广度优先算法 (2)递归法 3. 路径总和 (1)递归法 (2…...

Flask学习之项目搭建
一、项目基本结构 1、 exts.py 存在的目的:在Python中,如果两个或更多模块(文件)相互导入对方,就会形成导入循环。例如,模块A导入了模块B,同时模块B又导入了模块A,这就会导致导入循环。 比如在这个项目中…...

**CentOS7安装Maven**
CentOS7安装Maven 首先先解压压缩包apache-maven-3.9.9-bin.tar.gz tar -xvf apache-maven-3.9.9-bin.tar.gz解压完毕后配置环境变量 vim /etc/profile在环境变量配置文件中加入这句话 #Maven export MAVEN_HOME/opt/soft/maven362 //换成自己的路径 export PATH$PATH:$JAVA…...

(undone) MIT6.824 Lecture1 笔记
参考1MIT课程视频:https://www.bilibili.com/video/BV16f4y1z7kn/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 参考2某大佬笔记:https://ashiamd.github.io/docsify-notes/#/study/%E5%88%86%E5%B8%83%…...

小白投资理财 - 开篇
小白投资理财 - 开篇 第一健身第二提升工作技能第三理财自律和规划 我认为的人生三件大事值得投资,一是强身健体,有个好身体;二是提升工作技能,不断学习工作领域里的新知识;三是投资理财,确保资产不贬值。 …...

高中还来得及选择信息学奥赛赛道吗?
随着信息学奥赛(NOI)在升学中的重要性日益凸显,越来越多的学生和家长将其视为进入顶尖高校的一个重要途径。然而,很多学生可能直到高中阶段才意识到信息学奥赛的重要性,或者才开始对编程产生兴趣。于是问题出现了&…...

01_OpenCV图片读取与展示
import cv2 img cv2.imread(夕阳.jpg, 1) #cv2.imshow(image, img) #此行只能命令行处py文件执行,会弹出一个视频窗口 #cv2.waitKey (0)以下会在jupyter Lab控件中显示读取的图像 #bgr8转jpeg格式 import enum import cv2def bgr8_to_jpeg(value, quality75):ret…...

C语言中的输入控制重要基础
在C语言编程中,处理输入数据是一个常见的任务。根据不同的情况,我们可以采用不同的输入控制方法。本文将介绍三类输入控制方式,分别是已知数据组数的输入、以特定符号结束的输入,以及以EOF结束的输入。 1. 已知数据组数的输入 在…...

Vue 学习
使用 vue 创建一个项目 检查是否已经安装了 npm 和 node npm --version node --version 使用 npm 安装 vue npm install -g vue/cli 检查 vue 工具是否安装成功 vue --version 使用 vue 工具创建一个名为 vue-router-syntax 的项目 这是命令行的创建方式 vue create vu…...

Redis集群的两种方式
1.Redis集群 1.1 搭建主从集群 单节点Redis的并发能力是有上限的,要进一步提高Redis的并发能力,就需要搭建主从集群,实现读写的分离。一般情况下,主节点负责写操作,从节点负责读操作。而从节点如何得知数据呢ÿ…...

QT--基础
将默认提供的程序都注释上意义 0101.pro QT core gui #QT表示要引入的类库 core:核心库 gui:图形化界面库 #如果要使用其他库类中的相关函数,则需要加对应的库类后,才能使用 greaterThan(QT_MAJOR_VERSION, 4): QT wid…...

一、前后端分离及drf的概念
1.1什么是前后端分离 程序角度 前后端不分离:一个程序(如django),接收请求处理HTML模版用户返回 前后端分离:两个程序 --前端:vue.js/react.js/angular.js --后端:Django drf(django rest framework) 2.专业角度 --…...

AI垃圾溢出识别摄像机
随着城市化进程的加快,垃圾处理成为城市管理中的一项重要工作。然而,垃圾桶溢出现象经常发生,给城市环境卫生和市民生活带来不便。为了解决这一问题,AI垃圾溢出识别摄像机 应运而生,利用人工智能技术,实现对…...

【抽代复习笔记】29-群(二十三):生成子群的两道例题及子群陪集的定义
例1:取S3的子集S {(12),(123)},S的生成子群包含哪些元?一个群的两个不同的子集会不会生成相同的子群? 解:(1)S的生成子群就是S3。证明[有不理解之处可以回头看看第27篇笔记中生成子群的定…...

安全防护装备检测系统源码分享
安全防护装备检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer…...

easyexcel常见问题分析
文章目录 一、读取数字多了很多小数位的精度问题 一、读取数字多了很多小数位的精度问题 浮点型转成BigDecimal的时候会出现精度问题,例如 这儿设置的实体类对象类型是String,默认用到的是StringNumberConverter转换器 2.1.4 版本 public class Strin…...

精通推荐算法31:行为序列建模之ETA — 基于SimHash实现检索索引在线化
1 行为序列建模总体架构 2 SIM模型的不足和为什么需要ETA模型 SIM实现了长周期行为序列的在线建模,其GSU检索单元居功至伟。但不论Hard-search还是Soft-search,都存在如下不足: GSU检索的目标与主模型不一致。Hard-search通过类目属性来筛选…...

Python知识点:如何使用Python进行卫星数据分析
开篇,先说一个好消息,截止到2025年1月1日前,翻到文末找到我,赠送定制版的开题报告和任务书,先到先得!过期不候! 如何使用Python进行卫星数据分析 卫星数据分析是地球观测领域的一项关键技术&a…...

Python实现Phong着色模型算法
目录 使用Python实现Phong着色模型算法引言Phong着色模型的基本原理1. 模型组成2. 公式 Phong着色模型的Python实现1. 向量类的实现2. 光源类的实现3. 材质类的实现4. Phong着色器类的实现 整体实现总结 使用Python实现Phong着色模型算法 引言 在计算机图形学中,光…...

异步框架 fastapi -- 连接mysql数据库
文章目录 docker部署mysqlfastapi连接mysql docker部署mysql 拉取mysql镜像 # 查看docker 服务状态 systemctl status docker systemctl start docker # 设置 开机启动 systemctl enable docker# 拉取mysql 镜像 docker search mysql:latest # 不指定版本时,默认…...

Spring 全家桶使用教程 —— 后端开发从入门到精通
Spring 全家桶是 Java 后端开发的利器,提供了从基础开发到复杂微服务架构的一整套解决方案。通过对各个 Spring 组件的掌握,开发者可以快速构建高效、稳定的企业级应用。本文将详细介绍 Spring 全家桶的各个组件,帮助开发者深入理解其核心功能…...

AI动漫转真人终极教程!3步做出爆款内容,音乐推广号变现
从小到大,我们看过的动漫、玩过的游戏有很多很多 但我们会发现里面的角色或者人物都是二次元的 我就会好奇这些动漫人物在现实中会长什么样 而现在,我们通过AI绘画竟然就能还原出来他们现实中的样子 除了动漫角色和游戏人物,古代的画像、…...

vue2 vconsole有助于移动端开发页面调试
项目场景: pc项目开发中,有浏览器自带的调试工具。但在移动端,就需要自己搭建调试工具了。vconsole一种非常方便的前端调试依赖库,有助于我们在移动端开发式进行调试,快速排查移动端问题。 搭建步骤 1、安装依赖库。…...

别再使用[]来获取字典的值了,来尝试一下这些方法
字典 在Python中,字典(Dictionary)是一种非常灵活的数据结构,用于存储键值对(key-value pairs)。每个键都是唯一的,并且与某个值相关联。字典是Python中处理映射关系(即一个键对应一…...

如果你不愿意冒一切风险,就不要成为创业者:如何建立一个年收入 1800 万美元的支付业务
作者:Austin Mac Nab,VizyPay 的 CEO 兼创始人 在创业初期,如果有人告诉我,我需要冒一切风险才能成功,我大概会吓得绕道而行。但事实是,如果你不愿意冒一切风险,就不要成为创业者。本着这个信念…...

4.浮点数二分【求数的平方根】
模板 public class BinarySearch {// 检查x是否满足某种性质public static boolean check(double x) {// 实现具体的检查逻辑return false; // 这里仅为示例,实际根据需求修改}public static double bsearch_3(double l, double r) {final double eps 1e-6; // …...

简站wordpress主题产品多图ACF插件设置方法
此教程仅适用于演示站有产品多图的主题,演示站没有产品多图的主题,就别往下看了,省得浪费时间。 1、给产品添加轮播图 简站wordpress主题有多个产品图的主题,添加产品轮播图的具体方法如下: 1.2、选择产品分类 添加…...

USB设备在Linux系统中的识别和加载过程
文章目录 一、USB设备的插入与检测二、中断处理与设备识别三、驱动程序加载与设备注册四、设备节点创建与权限分配五、设备初始化与通信 在Linux系统中,USB设备的自动识别和加载过程是一个高效且复杂的机制,确保了用户能够无缝地使用这些设备。本文将深入…...

nacos通过@Value动态刷新配置
Value获取最新值 引入jar包: <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-nacos-config</artifactId><version>2.2.1.RELEASE</version> </dependency>引入配置…...

[研发工具箱] 系列3.机电类常用的分类网站
工具箱系列1里,我们对国家标准馆提供的服务做了一些简介,在研发工作中还有一些非常宝贵的资讯来源,现在尽可能多的列举出一些宝贝网站: 1.文献标准类网站: 我经常会用到3 NTSL国家科技图书文献中心 之前提到的国家标…...