题目
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 分析有些人用map保存所有元素并计数出现次数，然后利用k，在map中寻找k-val，也可以在每次找到一个节点时，对其进行从根节点开始的二叉搜索树遍历。
/** * 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 searchVal(TreeNode* root,TreeNode* Root,int k){//全局搜索k bool find=false; TreeNode* temp=Root; if(Root==NULL) return find; if(Root->val==k&&root!=Root){//如果有k值并且与之前的节点不一样，则返回true find=true; return find; } else if(k<Root->val){//否则去左右子树搜索 return searchVal(root,Root->left,k); } else return searchVal(root,Root->right,k); } bool findTarget(TreeNode* root, TreeNode* Root, int k) { bool find=false; if(root==NULL) return find; if(root->right!=NULL){//当右子树不为空时，搜索右子树里面有没有该值 find|=findTarget(root->right,Root,k); } if(root->left!=NULL){ find|=findTarget(root->left,Root,k); } find|=searchVal(root,Root,k-root->val);//全局搜索有没有k-root->val，其中root记录当前节点的指针，Root记录二叉搜索树的根节点指针 return find; } bool findTarget(TreeNode* root, int k){ return findTarget(root,root,k); } };