在leetCode看到一题目
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: TrueExample 2:
Input:
5
/ \
3 6
/ \ \
2 4 7 Target = 28 Output: False
于是用js造一棵树，然后尝试实现
/**
* [tree 树]
* val 节点值
* leftTree 左树(null代表没有左树)
* rightTree 右树(null代表没有右树)
*/
var myTree = {
val: 5,
leftTree:{
val: 3,
leftTree:{
val: 2,
leftTree: null,
rightTree: null
},
rightTree: {
val: 4,
leftTree: null,
rightTree: null
}
},
rightTree:{
val: 6,
leftTree: null,
rightTree: {
val: 7,
leftTree: null,
rightTree: null
},
}
} //主方法
function findTarget(tree, k) {
//用于存储遍历过的节点的值
var set = [];
//查找
return find(tree, k, set);
} //查找方法
function find(tree, k, set){
//如果节点为空直接返回false,不需要考虑根节点为空的情况，因为不可能
if(null == tree){
return false;
} //看集合中是否包含 目标数(k)-节点值(root.val)
if(set.indexOf(k-tree.val) > -1){
return true;
} //将当前节点值存进集合
set.push(tree.val); //对本树的左右节点进行判断，递归
return find(tree.leftTree, k, set) || find(tree.rightTree, k, set);
} //testing
console.log(findTarget(myTree, 14));
java版的
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//主方法
public boolean findTarget(TreeNode root, int k) {
//用于存储遍历过的节点的值
HashSet<Integer> set = new HashSet<Integer>();
//查找
return find(root, k, set);
} //查找方法
public boolean find(TreeNode root, int k, HashSet<Integer> set){
//如果节点为空直接返回false,不需要考虑根节点为空的情况，因为不可能
if(null == root){
return false;
} //看集合中是否包含 目标数(k)-节点值(root.val)
if(set.contains(k-root.val)){
return true;
} //将当前节点值存进集合
set.add(root.val); //对本树的左右节点进行判断，递归
return find(root.left, k, set) || find(root.right, k, set);
}
}