LeetCode 653. Two Sum IV - Input is a BST(两个数的和 IV - 输入是二叉搜索树)
题目描述
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
解法一
思路
如果单纯地把BST想象成是一个无序数组,那这题该怎么做呢?注意到题目并不要求返回具体哪两个数可以组成target,所以只需要维护一个set
,用来保存期望的元素值;在遍历到每个元素的时候,首先检查set
中有没有值与当前元素值相等,有则返回True
,否则把target与当前元素值的差(期望元素值)放到set
中;如果中途没有返回,则最后返回False
,表示没有匹配的元素。
如上所述是对于无序数组的处理,那回到BST呢?只需要遍历BST就好了,遍历BST实际上就相当于是在遍历无序数组。
Python
class Solution:
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
candidates = set()
stack = []
while stack or root:
if root:
val = root.val
if val in candidates:
return True
else:
candidates.add(k - val)
stack.append(root)
root = root.left
else:
node = stack.pop()
root = node.right
return False
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> candidates = new HashSet<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
int val = root.val;
if (candidates.contains(val)) {
return true;
} else {
candidates.add(k - val);
}
stack.add(root);
root = root.left;
} else {
TreeNode node = stack.pop();
root = node.right;
}
}
return false;
}
}
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool findTarget(TreeNode *root, int k) {
unordered_set<int> candidates;
stack<TreeNode *> sta;
while (!sta.empty() || root != nullptr) {
if (root != nullptr) {
int val = root->val;
if (candidates.find(val) != candidates.end()) {
return true;
} else {
candidates.insert(k - val);
}
sta.push(root);
root = root->left;
} else {
TreeNode *node = sta.top();
sta.pop();
root = node->right;
}
}
return false;
}
};