电子商务网站建设内容,网站上传 空间 数据库,vr技术对网站建设的影响,佛山网站建设公司哪专业二叉查找树#xff08;BST#xff09;#xff1a;根节点大于等于左子树所有节点#xff0c;小于等于右子树所有节点。 二叉查找树中序遍历有序。 ❓501. 二叉搜索树中的众数
难度#xff1a;简单
给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root… 二叉查找树BST根节点大于等于左子树所有节点小于等于右子树所有节点。 二叉查找树中序遍历有序。 ❓501. 二叉搜索树中的众数
难度简单
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值结点右子树中所含节点的值 大于等于 当前节点的值左子树和右子树都是二叉搜索树
示例 1 输入root [1,null,2,2] 输出[2] 示例 2 输入root [0] 输出[0] 提示
树中节点的数目在范围 [ 1 , 1 0 4 ] [1, 10^4] [1,104] 内 − 1 0 5 N o d e . v a l 1 0 5 -10^5 Node.val 10^5 −105Node.val105
进阶 你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内
思路
中序遍历边遍历边统计
要设置三个变量curCnt表示当前个数maxCnt表示最大个数preNode表示前一个结点
如果当前结点值等于前一个结点值则curCnt否则curCnt置为1重新计数如果当前个数curCnt大于最大个数maxCnt则将数组清空添加当前节点值如果当前个数curCnt大于最大个数maxCnt则不需要清空在数组后面添加就行
代码(Java、C)
Java
class Solution {private int curCnt 1;private int maxCnt 1;private TreeNode preNode null;public int[] findMode(TreeNode root) {ListInteger maxCntNums new ArrayList();inOrder(root, maxCntNums);int[] ret new int[maxCntNums.size()];int idx 0;for (int num : maxCntNums) {ret[idx] num;}return ret;}private void inOrder(TreeNode node, ListInteger nums) {if (node null) return;inOrder(node.left, nums);if (preNode ! null) {if (preNode.val node.val) curCnt;else curCnt 1;}if (curCnt maxCnt) {maxCnt curCnt;nums.clear();nums.add(node.val);} else if (curCnt maxCnt) {nums.add(node.val);}preNode node;inOrder(node.right, nums);}
}C
class Solution {
public:int curCnt 1;int maxCnt 1;TreeNode* preNode nullptr;vectorint findMode(TreeNode* root) {vectorint ans;inOrder(root, ans);return ans;}void inOrder(TreeNode* root, vectorint ans){if(root nullptr) return;inOrder(root-left, ans);if(preNode ! nullptr){if(root-val preNode-val) curCnt;else curCnt 1;}if(curCnt maxCnt){maxCnt curCnt;ans.clear();ans.push_back(root-val);}else if(curCnt maxCnt){ans.push_back(root-val);}preNode root;inOrder(root-right, ans);}
};运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)即遍历这棵树的复杂度。空间复杂度 O ( 1 ) O(1) O(1)如果调用栈的开销不被计算在内储存结果的数组也不计算空间复杂度为 O ( 1 ) O(1) O(1)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
