大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。
1-1：题目描述
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [1,null,2,2]
Output: [2]
Example 2:
Input: root = [0]
Output: [0]
Constraints:
The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
通过次数74,211提交次数143,326
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1-2：朴素解法
☘️最朴素的思路就是，遍历完所有的节点，用hashmap来存储所有的数字出现的次数，最后从hashmap中找出出现次数最大的，还是比较容易的，所以这里也就忽略了。用到了额外的空间，所以直接去研究难一些的，常数级的解法吧。
1-3：O(N)空间复杂度
☘️as we all know，二叉搜索树的中序遍历一定是一个递增序列，所以最频繁出现次数最多的，在这个递增序列中一定是连续存在的，比如1，1，2，2，2这种。我们的任务就是将最多出现的值收集起来。那么整个过程中主要遇到的问题就是：
- 最多出现的值可能不止一个，比如1，1，2，2这种，因为这个特点，难度直接就上去了，以至于我想到了这个思路也没写出来。。。
☘️算法流程：
☘️用一个base代表出现重复值的起点，count代表重复值出现的次数，maxCount代表出现次数最多的。在值比较的时候会出现两种情况：
- 值和base相等
- 很自然，count++，如果count > maxcount值的话，就替换掉maxCount。
- 值和base不相等
- 重置count=1，base也重置为新的值。
☘️写到这的时候，我一开始也以为结束了，但是，还有一个新的问题，那就是，万一所有的只出现了一次呢？那么是不是 在值后面得有一次这样的判断？
if (count == maxCount) {
result.add(base);
}
总的代码就变成这样：
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
maxCount = Math.max(count, maxCount);
} else {
count = 1;
base = root.val;
if (count == maxCount) {
result.add(base);
}
}
traverse(root.right);
}
☘️是的，得有。你以为又结束了，还没有！加入我是1，2，2新的值2出现了2次，2次得代替原来的1是吧，那么就得先清除结果集，再加入新的值。于是变成这样：
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
} else {
count = 1;
base = root.val;
if (count == maxCount) {
result.add(base);
}
}
traverse(root.right);
}
☘️下面再初始化一下，base默认是无穷值，count=maxcount=0，也就是不存在，这样遇见第一个值的时候，第一个值就会变成base，这样比较好理解。
List<Integer> result = new ArrayList<>();
int base = Integer.MIN_VALUE;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
if (root == null) {
return null;
}
traverse(root);
int[] mode = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
mode[i] = result.get(i);
}
return mode;
}
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
} else {
count = 1;
base = root.val;
if (count == maxCount) {
result.add(base);
}
}
traverse(root.right);
}
先系系吧~
☘️肉眼看不出代码哪里出现了问题，那就debug下。
☘️debug的时候你就会发现，当只有一个节点的时候，在算法最开始的时候，maxcount也会更新一次。所以这个时候也得添加一次result。
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
} else {
count = 1;
base = root.val;
if (count == maxCount) {
result.add(base);
}
if (count > maxCount) {
maxCount = count;
// result.clear();
result.add(base);
}
}
traverse(root.right);
}
☘️注意，这里一定要在count==maxcount之后判断。那么我继续提交。又又又出问题了，是的，很正常，哈哈哈，这次看看是哪里出了问题？
同样，我也debug起来，直到发现了问题。
☘️没错，当程序走到最后一个1的时候，发现，出现了count和maxcount相等的情况，也就是4个0之后出现了4个1了。所以，还得再加一个。
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
// 新加部分----------
if (count == maxCount) {
result.add(base);
}
//-------------------
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
} else {
count = 1;
base = root.val;
if (count == maxCount) {
result.add(base);
}
if (count > maxCount) {
maxCount = count;
// result.clear();
result.add(base);
}
}
traverse(root.right);
}
最终AC
☘️为了让代码看的优雅一点，我们修改一下，这样才能达到答案的最终代码：
List<Integer> result = new ArrayList<>();
int base = Integer.MIN_VALUE;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
if (root == null) {
return null;
}
traverse(root);
int[] mode = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
mode[i] = result.get(i);
}
return mode;
}
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
if (base == root.val) {
count++;
} else {
count = 1;
base = root.val;
}
if (count == maxCount) {
result.add(base);
}
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
traverse(root.right);
}
时间复杂度O(N)
空间复杂度O(H)，H是树高
☘️那么看到这结束了？还没有，我一开始也很疑惑，答案说了除了递归栈的额外空间这里不应该出现额外的空间使用了，对不对。但是这里不是出现了list了吗？我感觉应该是这样，答案最终使用数组存储的，这个数组存储本身就有点问题，因为数组的空间必须要提前开辟的，我们不知道树的节点的情况，不知道到底有几个众数呀，所以只能用list。把返回值改成list就完美了，并且已经符合题意。
1-4：O(1)常数级的空间复杂度
☘️要想搞明白这个，首先要了解Morris 算法，Morris算法的核心在于利用线索找到这个节点在二叉树中序遍历的后继位置，什么是后继呢？举个例子 1 2 3，中序遍历的结果就是 2 1 3，1就是2的后继，，2就是1的前驱。
☘️首先给出Morris算法的步骤：
- 首先，cur代表遍历指针，如果cur.left 为空，也就是说到了最左侧节点了，cur = cur.right（利用后继指针回到根的位置）.
- 如果 cur.left != null，有左孩子，就要设法找到cur的前驱节点，就得沿着左孩子一直往右下找，找到前驱节点记做pre。
- 如果pre.right == null，也就是没有构建好后继，则pre.right = cur,构建后继指针，指向cur，接着cur = cur.left
- 如果pre.right == cur，也就是说已经有后继节点了（等于就是之前已经经过cur这个节点了，之前没有visit，这次visit），cur = cur.right，转向右边继续算法。这里就像是左边访问完了，访问根，根访问完了换到右边继续访问。
public void traverse(TreeNode root) {
TreeNode cur = root;
TreeNode pre = null;
while (cur != null) {
if (cur.left == null) {
System.out.println(cur);
cur = cur.right;
// 加continue的作用就在于 最后的时候cur.right == null了，
// 运行pre = cur.left;空指针异常
continue;
}
pre = cur.left;
// 开始找最右侧的节点，也就是cur的前驱节点，
// 加pre.right != cur是因为，如果是已经构建后继的节点，pre.right会回到cur上，
// 就不是最右下的那个节点了
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 构建后继节点的过程
if (pre.right == null) {
pre.right = cur;
// cur继续向左构建后继节点
cur = cur.left;
}
// 已经构建了节点了，说明之前访问过pre了，这个时候开业继续访问cur了
if (pre.right == cur) {
pre.right = null;
System.out.println(cur);
cur = cur.right;
}
}
}
☘️如果你不能理解的话，就手动模拟一下，这里放一个我手动模拟的草稿，有点粗糙。。
☘️这个算法写完了，我们就可以运用到这道题目上来了。只需要把访问节点的操作换成下面的代码：
if (base == root.val) {
count++;
} else {
count = 1;
base = root.val;
}
if (count == maxCount) {
result.add(base);
}
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
最终代码如下：
class Solution {
List<Integer> result = new ArrayList<>();
int base = Integer.MIN_VALUE;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
if (root == null) {
return null;
}
traverse(root);
int[] mode = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
mode[i] = result.get(i);
}
return mode;
}
private void update(TreeNode root) {
if (base == root.val) {
count++;
} else {
count = 1;
base = root.val;
}
if (count == maxCount) {
result.add(base);
}
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(base);
}
}
public void traverse(TreeNode root) {
TreeNode cur = root;
TreeNode pre = null;
while (cur != null) {
if (cur.left == null) {
// System.out.println(cur);
update(cur);
cur = cur.right;
// 加continue的作用就在于 最后的时候cur.right == null了，
// 运行pre = cur.left;空指针异常
continue;
}
pre = cur.left;
// 开始找最右侧的节点，也就是cur的前驱节点，
// 加pre.right != cur是因为，如果是已经构建后继的节点，pre.right会回到cur上，
// 就不是最右下的那个节点了
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
// 构建后继节点的过程
if (pre.right == null) {
pre.right = cur;
// cur继续向左构建后继节点
cur = cur.left;
}
// 已经构建了节点了，说明之前访问过pre了，这个时候开业继续访问cur了
if (pre.right == cur) {
pre.right = null;
// System.out.println(cur);
update(cur);
cur = cur.right;
}
}
}
}
时间复杂度O(N)，每个节点的访问不会超过两次
空间复杂度O(1)
☘️但是真正做到了，空间复杂度O(1)。
1-5：总结
☘️今天最主要的就是，这个Morris算法了，不用额外空间就可以完成二叉树的中序遍历，核心思想就是利用前驱和后继，类似于线索二叉树的思想。秒啊！秒啊！感觉上面的O(N)空间复杂度需要写对，就很不容易了，出现的情况有很多。
点个赞嘛~哥哥~，下次再来奥~美女！