3-Two Sum IV - Input is a BST
题目
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
案例 1:
输入: 5 / 3 6 / 2 4 7
Target = 9
输出: True
>
案例 2:
输入: 5 / 3 6 / 2 4 7
Target = 28
输出: False
解答
第一种思路：整理成数组，回到two sum 2
把二叉树变成原来的升序数组，然后再用two sum 2的解法来做
二分法
var findTarget = function (root, target) {
if (!root) { // 基础判断
return false;
}
let nums = []
function inOrder(root) {
if (!root) {
return;
}
inOrder(root.left);
nums.push(root.val);
inOrder(root.right);
}
inOrder(root);
// 以下是二分法的代码
for (let index = 0; index < nums.length; index++) {
const aim = target - nums[index];
let start = index + 1;
end = nums.length - 1;
while (start <= end) {
let mid = Math.round((start + end) / 2)
if (nums[mid] === aim) {
return true
} else if (nums[mid] < aim) {
start = mid + 1
} else {
end = mid - 1
}
}
}
return false
};Runtime: 88 ms, faster than 81.75% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 41.5 MB, less than 78.42% of JavaScript online submissions forTwo Sum IV - Input is a BST.
双指针
var findTarget = function (root, target) {
...
let low = 0;
high = nums.length - 1;
while (low < high) {
let sum = nums[low] + nums[high];
if (sum < target) {
low++
} else if (sum > target) {
high--
} else {
return true
}
}
return false
};Runtime: 88 ms, faster than 81.75% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 42.1 MB, less than 39.72% of JavaScript online submissions for Two Sum IV - Input is a BST.
好像表现也差不多
一遍哈希表
var findTarget = function (root, target) {
...
const arrMap = new Map()
for (let i = 0; i < nums.length; i++) {
const result = target - nums[i];
if (arrMap.has(result)) {
return true
}
arrMap.set(nums[i], i)
}
return false
};Runtime: 76 ms, faster than 97.74% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 41.7 MB, less than 66.44% of JavaScript online submissions forTwo Sum IV - Input is a BST.
用对象呢？
var findTarget = function (root, target) {
...
const map = {}
for (let i = 0; i < nums.length; i++) {
const result = target - nums[i];
if (map.hasOwnProperty(result)) {
return true
}
map[nums[i]] = i;
}
return false
};Runtime: 104 ms, faster than 32.73% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 42.9 MB, less than 13.01% of JavaScript online submissions for Two Sum IV - Input is a BST.
总是要比map差一点，也不知道为什么
哈希表+两分法
和two sum 2的方法不同，需要多做一步判断，不然会出现多次用同一个数的情况。例子是[2,3]，target=6，显然是应该返回false。然而不加判断会返回true。
第一遍找不到4，于是把访问过的3加入哈希表{3 => 1}
第二遍开始查哈希表，要找3，正好有3，就返回了true。然而这两个3都是nums的第二位，用了同一个数字了。
在two sum2中可以实现，因为给的target总是对的，因此就不会出现这种的情况，也就不需要多加一步判断了。
var findTarget = function (root, target) {
...
const arrMap = new Map()
for (let i = 0; i < nums.length; i++) {
const aim = target - nums[i];
if (arrMap.has(aim) && arrMap.get(aim) !== i) { // 这里需要多做一步判断
return true
}
let start = i + 1;
end = nums.length - 1;
while (start <= end) {
let mid = Math.round((start + end) / 2)
if (nums[mid] === aim) {
return true
} else if (nums[mid] < aim) {
start = mid + 1
} else {
end = mid - 1
}
arrMap.set(nums[mid], mid)
}
}
return false
};Runtime: 120 ms, faster than 13.88% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 41.7 MB, less than 67.50% of JavaScript online submissions for Two Sum IV - Input is a BST.
第二种思路：用二叉树的特性
跳过理顺为数组的环节，直接一个个拿出来比对
深度优先搜索
var findTarget = function (root, k) {
let stack = [root] // 数组初始化，存入root
let map = []
while (stack.length > 0) {
let cur = stack.pop() // 每次把数组顶端的node拿出来
if (map.includes(k - cur.val)) { // 在map数组内查询是否有
return true
}
map.push(cur.val) // 没有就推入map数组
if (cur.left) {
stack.push(cur.left)
}
if (cur.right) {
stack.push(cur.right)
}
}
return false
};因为右边是最后推入stack的，因此是从右往左的深度优先的查询。
Runtime: 152 ms, faster than 5.88% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 42 MB, less than 45.20% of JavaScript online submissions forTwo Sum IV - Input is a BST.
不过感觉非常耗时……也许是因为map是数组的原因？.includes()查询比较耗时？
换成obj呢？
var findTarget = function (root, k) {
...
let map = {}
...
if (map.hasOwnProperty(k - cur.val)) {
return true
}
map[cur.val] = true
...
};Runtime: 108 ms, faster than 27.23% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 42.9 MB, less than 13.93% of JavaScript online submissions for Two Sum IV - Input is a BST.
耗时降低了，但占用的内存增加了。这是在用空间换时间。
换成map呢？
var findTarget = function (root, k) {
...
let map = new Map()
...
if (map.has(k - cur.val)) {
return true
}
map.set(cur.val, true)
...
};Runtime: 104 ms, faster than 32.53% of JavaScript online submissions for Two Sum IV - Input is a BST.
Memory Usage: 41.5 MB, less than 82.14% of JavaScript online submissions for Two Sum IV - Input is a BST.
似乎总是map最快
既然知道了要找的内容，可以直接用二叉树找啊
思路分为两套循环，外循环是深度优先的遍历，内循环是根据当前节点val的二叉树的搜索。 曾经搜索过的，就放在map当中，启动内循环之前先看map当中有没有。
难点在于怎么判断在二叉树上的不同节点。换言之，在map中找到的值不是他自己。【哈希表+两分法中遇到的问题】 也就是二叉树的定位问题。。
感觉可以多保存一下位置信息，但即使能做到也把问题变得更加复杂了。。
测试代码
生成二叉树：
/**
* @param {number[]} keys
* @return {TreeNode} root
*/
function BST(keys) {
let root = null;
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
const insertNode = (node, newNode) => {
if (node.val > newNode.val) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
const insert = val => {
const newNode = new TreeNode(val);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
keys.forEach(key => {
if (key) {
insert(key);
}
});
return root;
}使用：
const tree = BST([5, 3, 6, 2, 4, null, 7]);
// TreeNode {val: 5, right: TreeNode, left: TreeNode}这只实现了把数据插入二叉树，而没有实现树的旋转，因此如果输入了[-1, 5, 7, 11]，就会出现只有右边一串树的情况，就变成了链表？ 不过测试用例不需要太精细，毕竟传入的node都是处理好的平衡树。
二叉树参考
Last updated
Was this helpful?