温州网站快速排名,成都网站seo报价,做年报的网站怎么登不上去了,asp.net网站加速题意理解#xff1a; 首先明确#xff1a; 二叉搜索树中序遍历是严格的单调递增序列#xff0c;也就是说#xff0c;传统意义上得到二叉搜索树不存在相同的数#xff0c;也不可能存在众数。 所以#xff1a; 这里的二叉搜索树不是严格意义上的二叉搜索树#xf… 题意理解 首先明确 二叉搜索树中序遍历是严格的单调递增序列也就是说传统意义上得到二叉搜索树不存在相同的数也不可能存在众数。 所以 这里的二叉搜索树不是严格意义上的二叉搜索树它允许重复的值其中序遍历是不严格的单调增的序列。 又因为 二叉搜索树是不严格的单调增序列所以其相同的值总是挨着的 所以 我们能从前后不相同的两个值为一个起始点统计相同数的个数 所以 我们能维护一个最大的count在整个遍历在整个过程中并保存对应的元素值 解题思路 对应两种树的遍历思路 递归 迭代 1.递归
中间节点的处理逻辑是
pre的值等于cur的值时统计当前元素的count否则count开启重置count1
对maxCount进行更新 若当前countmaxCount,则当前root的值进入结果集 若当前countmaxCount则当前结果集清空root的值进入结果集maxCountcount值更新 若当前countmaxCount,无操作
/*** 这里找二叉搜索树的众数首先明确正常的二叉搜索数不存在重复的数据其中序遍历是严格单调增序列* 所以这里的二叉树是非常规的二叉树它允许重复的值重复的值总是存在于左子树* 同时又因为二叉搜索树中序遍历是有序的所以重复的数总是挨着的可以一个起始点开始count,统计出现次数* param root* return*///保存结果ListInteger resultListnew ArrayList();//双指针是想前一个节点TreeNode prenull;//记录当前元素重复次数int count0;//记录最大重复次数int maxCount0;//递归解法public int[] findMode(TreeNode root) {//中序遍历//左子树处理if(Objects.nonNull(root.left)) findMode(root.left);//中间节点处理if(prenull||pre.val!root.val){count1;}else{count;}//最大count更新if(maxCountcount){resultList.clear();resultList.add(root.val);maxCountMath.max(maxCount,count);}else if(maxCountcount){resultList.add(root.val);}// 节点推移preroot;//右子树处理if(Objects.nonNull(root.right)) findMode(root.right);//list转数组return resultList.stream().mapToInt(Integer::intValue).toArray();}
2.迭代
迭代和递归的中间处理逻辑是相同的只是使用自定义栈来模拟递归过程来防止栈溢出
//迭代解法public int[] findMode2(TreeNode root){ListInteger resultListnew ArrayList();//双指针是想前一个节点TreeNode prenull;//记录当前元素重复次数int count0;//记录最大重复次数int maxCount0;//自定义栈StackTreeNode stacknew Stack();stack.push(root);while(!stack.isEmpty()){TreeNode curstack.peek();if(cur!null){stack.pop();//中序入栈有因为栈总是先进后出的所以以一下顺序入栈//对子树进行非空判断后入栈则子树不会导致null值入栈//手动null值入栈是一个信号即下一个值为中间节点一定是非空的进行识别并处理if(Objects.nonNull(cur.right)) stack.push(cur.right);stack.push(cur);stack.push(null);if(Objects.nonNull(cur.left)) stack.push(cur.left);}else{stack.pop();curstack.pop();//获得中间节点中间节点的处理逻辑if(prenull||pre.val!cur.val) count1;else count;if(maxCountcount){resultList.add(cur.val);} else if (maxCountcount) {resultList.clear();resultList.add(cur.val);maxCountcount;}precur;}}return resultList.stream().mapToInt(Integer::intValue).toArray();}
3.分析 时间复杂度 递归O(n) 迭代O(n) 空间复杂度 递归O(1) 迭代O(n)
