全网营销型网站建设模板,给公司起名字大全免费,网站制作专业的公司哪家好,百度一下浏览器下载安装给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;找出并返回 BST 中的所有 众数#xff08;即#xff0c;出现频率最高的元素#xff09;。
如果树中有不止一个众数#xff0c;可以按 任意顺序 返回。
假定 BST 满足如下定义#xf…给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树 提示
树中节点的数目在范围 [1, 104] 内
105 Node.val 105
进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
AC:
/** lc appleetcode.cn id501 langcpp** [501] 二叉搜索树中的众数*/// lc codestart
/*** 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* pre NULL;int count 0;int maxCount 0;vectorint result;void traversal(TreeNode* cur) {if(cur NULL)return ;traversal(cur-left);if(pre NULL)count 1;else if(pre-val cur-val){count;}else count 1;pre cur;if(count maxCount){result.push_back(cur-val);}if(count maxCount){maxCount count;result.clear();result.push_back(cur-val);}traversal(cur-right);return ;}vectorint findMode(TreeNode* root) {traversal(root);return result;}
};
// lc codeendTips
对于一次遍历完搜索二叉树将众数结果统计出来 if(count maxCount){result.push_back(cur-val);}if(count maxCount){maxCount count;result.clear();result.push_back(cur-val);}The first if statement checks if the count of the current value is equal to the maximum count seen so far (count maxCount). If the count is equal to the maximum count, then the current value is also a mode of the binary search tree, so the value is added to the result vector using the push_back function.
The second if statement checks if the count of the current value is greater than the maximum count seen so far (count maxCount). If the count is greater than the maximum count, then the current value is a new mode of the binary search tree, so the result vector is cleared using the clear function, and the current value is added to the result vector using the push_back function. Additionally, the maxCount variable is updated to reflect the new maximum count.
Overall, this block of code is a simple and efficient way to update the result vector with the mode(s) of a binary search tree. The code uses a straightforward approach to keep track of the count of each value in the binary search tree, and updates the result vector whenever a new mode is found. One possible way to improve the code would be to add error checking to ensure that cur is not a null pointer before accessing its value. Additionally, the variable names could be more descriptive to make the code easier to read and understand. 二叉树双指针的移动 pre cur;The line of code pre cur; is used to update the pre pointer to point to the current node cur. This is because the function is traversing the binary search tree in order, and pre needs to point to the previous node in order to calculate the count of each value in the binary search tree.
Specifically, the function uses an in-order traversal of the binary search tree to visit each node in ascending order. For each node, the function calculates the count of the node’s value by comparing it to the value of the previous node. If the value is the same as the previous node’s value, then the count is incremented. Otherwise, the count is reset to 1.
The pre pointer is used to keep track of the previous node visited during the in-order traversal. Initially, pre is set to nullptr to indicate that there is no previous node. For each node cur, the line of code pre cur; updates pre to point to cur, so that pre will point to the previous node during the next iteration of the loop.
Overall, this line of code is a simple and efficient way to update the pre pointer during an in-order traversal of a binary search tree. One possible way to improve the code would be to add error checking to ensure that pre and cur are not null pointers before updating pre. Additionally, the variable names could be more descriptive to make the code easier to read and understand.
