中序遍历 迭代
解题思路
迭代的方式进行中序遍历，定义一个次数 count ，每遍历一次 count++；
当
count === k的时候，返回当前节点的值；
复杂度
-
时间复杂度：
O(h+k)，先到达叶子位置 h（最小节点位置），复杂度为O(h)，然后找到第 k 小的元素，复杂度为O(k)； -
空间复杂度：
O(h)；
代码实现
var kthSmallest = function (root, k) {
let count = 0;
let stack = [];
while (root || stack.length) {
while (root) {
stack.push(root);
root = root.left;
}
root = stack.pop();
count++;
if (count === k) return root.val;
root = root.right;
}
};
中序遍历 递归
解题思路
递归遍历时计数，统计当前节点的序号；
递归到第 k 个节点时，应记录结果 res；
记录结果后，后续的遍历即失去意义，应 提前返回；
复杂度
-
时间复杂度：
O(N)，当树退化为链表，即全部为左子节点时，无论 k 的值大小，递归深度都为 N； -
空间复杂度：
O(N)，当树退化为链表时，系统使用O(N)大小的栈空间；
代码实现
let res, k;
var dfs = (root) => {
if (root === null) return;
dfs(root.left);
if (k === 0) return; // 提前停止递归
if (--k === 0) res = root.val;
dfs(root.right);
};
var kthSmallest = function (root, target) {
k = target;
dfs(root);
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 653. 两数之和 IV - 输入二叉搜索树
上一篇
评论
