LeetCode 501. 二叉搜索树中的众数
https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
难度:简单
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
-
结点左子树中所含结点的值小于等于当前结点的值
-
结点右子树中所含结点的值大于等于当前结点的值
-
左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2]
,
1
\
2
/
2
返回 [2]
提示:如果众数超过1个,不需考虑输出顺序
进阶: 你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
解法1:中序遍历
对于一棵二叉搜索树,若对其进行中序遍历并在遍历过程中顺序记录节点值,那么记录的值会是一个单调递增序列(在本题中是单调不减序列)。
这样的话,若要求众数,我们可以先对其进行中序遍历,众数在序列中的位置一定是连续的,如 [1, 2, 2, 2, 3]
。这样,我们对这个序列进行遍历并计数,就能够得到它的众数。
不过,为了避免使用额外空间,我们可以在遍历过程中就求出众数,具体做法是维护一个 max
,表示当前所遇到的最多的连续数字的个数,然后在遍历过程中累计每个数字出现的次数,若比 max
大,则使用当前数字覆盖结果数组,并更新 max
值。
在中序遍历完成之后,我们还需要最后进行一次众数判断,因为最后的连续数字不会在遍历过程中判断是否是众数。
JS 代码:
var findMode = function(root) {
let res = [];
if (!root) {
return res;
}
let n;
let count = 0;
let max = -1;
const dfs = (node) => {
if (!node) {
return;
}
dfs(node.left);
if (n === undefined) {
n = node.val;
count = 1;
} else if (n === node.val) {
count++;
} else { // 遇到新的数字
if (count > max) {
max = count;
res = [n];
} else if (count === max) {
res.push(n);
}
n = node.val;
count = 1;
}
dfs(node.right);
};
dfs(root);
if (count > max) {
max = count;
res = [n];
} else if (count === max) {
res.push(n);
}
return res;
};
C 版本:
int max;
int count;
int cur;
void dfs(struct TreeNode* root, int* res, int* returnSize) {
if (!root) {
return;
}
dfs(root->left, res, returnSize);
if (count == -1) {
cur = root->val;
count = 1;
} else if (cur == root->val) {
count++;
} else {
if (max < count) {
max = count;
*returnSize = 0;
res[(*returnSize)++] = cur;
} else if (max == count) {
res[(*returnSize)++] = cur;
}
cur = root->val;
count = 1;
}
dfs(root->right, res, returnSize);
}
int* findMode(struct TreeNode* root, int* returnSize){
*returnSize = 0;
int *res = malloc(sizeof(int) * 4001);
count = -1;
max = -1;
if (!root) {
return res;
}
dfs(root, res, returnSize);
if (max < count) {
max = count;
*returnSize = 0;
res[(*returnSize)++] = cur;
} else if (max == count) {
res[(*returnSize)++] = cur;
}
return res;
}
解法2:Morris 算法
所有能使用中序遍历解决的问题都能使用 Morris 算法来优化其空间复杂度。
在使用 Morris 算法时最重要的是要把握好节点遍历的时机。
var findMode = function(root) {
let res = [];
if (!root) {
return res;
}
let n;
let count = 0;
let max = -1;
let pre;
const check = () => {
if (max < count) {
max = count;
res = [n];
} else if (max === count) {
res.push(n);
}
};
while (root) {
if (root.left) {
pre = root.left;
while (pre.right && pre.right !== root) {
pre = pre.right;
}
if (!pre.right) {
pre.right = root;
root = root.left;
} else {
// 此时是刚从左孩子节点返回之后,往右孩子遍历
if (n === undefined) {
n = root.val;
count = 1;
} else if (n === root.val) {
count++;
} else {
check();
n = root.val;
count = 1;
}
pre.right = null;
root = root.right;
}
} else {
// 节点此时可能是借助前面设置的空闲指针返回父节点,也可能是从父节点到右节点遍历的过程
if (n === undefined) {
n = root.val;
count = 1;
} else if (n === root.val) {
count++;
} else {
check();
n = root.val;
count = 1;
}
root = root.right;
}
}
check();
return res;
};
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!