深度优先搜索 DFS + 哈希表
解题思路
使用 深度优先搜索 的方式遍历整棵树，用哈希表记录遍历过的节点的值；
对于一个值为 x 的节点，检查哈希表中是否存在
k−x即可；
- 如果存在对应的元素，那么就可以在该树上找到两个节点的和为 k；
- 否则，将 x 放入到哈希表中；
如果遍历完整棵树都不存在对应的元素，那么该树上不存在两个和为 k 的节点；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树的大小； -
空间复杂度：
O(n)，其中 n 为二叉搜索树的大小，主要为哈希表的开销，最坏情况下需要将每个节点加入哈希表一次；
代码实现
var findTarget = function (root, k) {
const helper = (root, k) => {
if (root === null) return false;
if (set.has(k - root.val)) return true;
set.add(root.val);
return helper(root.left, k) || helper(root.right, k);
}
const set = new Set();
return helper(root, k);
};
广度优先搜索 BFS + 哈希表
解题思路
使用 广度优先搜索 的方式遍历整棵树，用哈希表记录遍历过的节点的值；
对于一个值为 x 的节点，检查哈希表中是否存在
k−x即可；
- 如果存在对应的元素，那么就可以在该树上找到两个节点的和为 k；
- 否则，将 x 放入到哈希表中；
如果遍历完整棵树都不存在对应的元素，那么该树上不存在两个和为 k 的节点；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树的大小； -
空间复杂度：
O(n)，其中 n 为二叉搜索树的大小，主要为哈希表的开销，最坏情况下需要将每个节点加入哈希表一次；
代码实现
var findTarget = function (root, k) {
const set = new Set();
const queue = [];
queue.push(root);
while (queue.length) {
const node = queue.shift();
if (set.has(k - node.val)) return true;
set.add(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 16. 最接近的三数之和
上一篇
评论
