深度优先遍历 DFS
解题思路
一想到二叉搜索树，就会想到中序遍历的结果是一个有序的序列；
根据此特性可利用双指针计算出重复元素数量，放入结果中：
- 如果后面出现了更大的 重复元素数量 则清空结果，重新放入；
- 如果后面出现了相等的 重复元素数量 则将该节点放入结果；
- 如果后面没有出现更大的 重复元素数量 则结果无需更新；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
实现代码
var findMode = function (root) {
let count = 0;
let maxCount = 1;
let pre = root;
let res = [];
const inorderTraversal = (cur) => {
// 1. 终止条件
if (cur === null) return;
inorderTraversal(cur.left);
// 2. 单层递归逻辑
pre.val === cur.val ? count++ : count = 1;
pre = cur;
if (count === maxCount) {
res.push(cur.val);
}
if (count > maxCount) {
res = [];
maxCount = count;
res.push(cur.val);
}
inorderTraversal(cur.right);
}
inorderTraversal(root);
return res;
}
广度优先遍历 BFS
解题思路
一想到二叉搜索树，就会想到中序遍历的结果是一个有序的序列；
根据此特性可利用双指针计算出重复元素数量，放入结果中：
- 如果后面出现了更大的 重复元素数量 则清空结果，重新放入；
- 如果后面出现了相等的 重复元素数量 则将该节点放入结果；
- 如果后面没有出现更大的 重复元素数量 则结果无需更新；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
实现代码
var findMode = (root) => {
let count = 0;
let maxCount = 1;
let pre = root;
let res = [];
const stk = [];
while (root || stk.length > 0) {
// 1. 一直向左查找，找到最左边的节点
while (root) {
stk.push(root);
root = root.left;
}
// 2. 出栈栈顶节点
root = stk.pop();
pre.val === root.val ? count++ : count = 1;
pre = root;
if (count === maxCount) {
res.push(root.val);
}
if (count > maxCount) {
res = [];
maxCount = count;
res.push(root.val);
}
// 3. 利用栈顶节点，去寻找右孩子节点
root = root.right;
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 530. 二叉搜索树的最小绝对差
上一篇
评论
