本文共 8061 字，大约阅读时间需要 26 分钟。

题目描述

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   7Target = 9Output: True

Example 2:

Input:     5   / \  3   6 / \   \2   4   7Target = 28Output: False

方法一、双重二叉树搜索

思路描述

• 创建两个指向二叉树的索引标签，一个用来遍历，一个用来搜索。实现一个树两种用途，在遍历的同时对遍历到的每一个元素进行的搜索

C语言实现（leetcode提交）

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; *//*    功能描述：遍历整棵二叉树，找到目标的结点*/bool findNumber(struct TreeNode *root,int target){
       bool isFind = false;    struct TreeNode *temp = root;    while(temp != NULL)    {
           if(target > temp->val)        {
               temp = temp->right;        }        else if (target < temp->val)        {
               temp = temp->left;        }        else        {
               isFind = true;            break;        }    }    return isFind;}bool preOrder(struct TreeNode* root,struct TreeNode *real_root,int target,bool *isflag){
       if(root == NULL)    {
           return ;    }    else    {
           if(root->left != NULL)        {
               preOrder(root->left,real_root,target,isflag);        }               if(root->right != NULL)        {
               preOrder(root->right,real_root,target,isflag);        }         if((target - root->val != root->val) && findNumber(real_root,target - root->val))        {
               *isflag = true;           return ;        }    }    return ;}bool findTarget(struct TreeNode* root, int k){
       //搜索树    bool isflag = false;    preOrder(root,root,k,&isflag);    return isflag;}

完整版C语言（包括构建二叉搜索树）

#include 
   
    #include 
    
     typedef enum{
   false,true} bool;//二叉树的结构体typedef struct TreeNode{
       int value;    struct TreeNode *left;    struct TreeNode *right;}TreeNode;typedef struct TreeNode *TreeList;bool BuildTree(TreeList* root, int array[],int arraySize);TreeNode *CreateNode(int value);bool ShowTree(TreeList root,int arraySize);bool findTarget(TreeNode* root, int k);bool findNumber(TreeNode* root,int target);bool preOrder(TreeNode* root,TreeNode *real_root,int target,bool *isflag);int main(){
       TreeList root = NULL;    int nums[] = {
   2,1,3};    int arraySize = 3;    printf("%d",BuildTree(&root,nums,arraySize));    printf("是否找到%d   ",findTarget(root,4));    return 0;}/*    功能描述：前序遍历*/bool preOrder(TreeNode* root,TreeNode *real_root,int target,bool *isflag){
       if(root == NULL)    {
           return ;    }    else    {
           if(root->left != NULL)        {
               preOrder(root->left,real_root,target,isflag);        }        if(root->right != NULL)        {
               preOrder(root->right,real_root,target,isflag);        }        printf("%d",target - root->value);        if(findNumber(real_root,target - root->value) && (target - root->value != root->value))        {
              *isflag = true;           return;        }    }    return ;}/*    功能描述：遍历整棵二叉树，找到目标的结点*/bool findNumber(TreeNode *root,int target){
       bool isFind = false;    TreeNode *temp = root;    while(temp != NULL)    {
           if(target > temp->value)        {
               temp = temp->right;        }        else if (target < temp->value)        {
               temp = temp->left;        }        else        {
               isFind = true;            break;        }    }    return isFind;}bool findTarget(TreeNode* root, int k){
       //搜索树    bool isflag = false;    preOrder(root,root,k,&isflag);    return isflag;}TreeNode *CreateNode(int value){
       TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));    node->value = value;    node->left = NULL;    node->right = NULL;}bool BuildTree(TreeList* root,int array[],int arraySize){
       if(arraySize <= 0)    {
           return false;    }    *root = (TreeNode *)malloc(sizeof(TreeNode));    *root = CreateNode(array[0]);    TreeList temp = NULL;    for(int i = 1;i < arraySize;i ++)    {
           temp = *root;        while(1) {
               if(array[i] > temp->value) {
                   if(temp->right == NULL) {
                       temp->right = (TreeNode *)malloc(sizeof(TreeNode));                    temp->right = CreateNode(array[i]);                    break;                }                temp = temp->right;            } else if(array[i] < temp->value) {
                   if(temp->left == NULL) {
                       temp->left = (TreeNode *)malloc(sizeof(TreeNode));                    temp->left = CreateNode(array[i]);                    break;                }                temp = temp->left;            }        }    }    return true;}
    
   

分析总结

• 注意，二叉搜索树种所有的元素都是的唯一的，不存在两个相同的元素。当一树两用的时候，很容易出现同一个元素检索到自身，注意排除这种情况，否则会出现如下的错误

  input：{1}，target：2，2-1=1，刚好等于自身

• 注意，我当采用的是后序遍历的时候，因为是递归，所以会造成多层嵌套的情况。一个return，仅仅是返回上一层，并不是返回所有的层。如果不加上标签量isflag，会继续比较遍历剩余的元素，并且以最后一层为最终的返回结果。

• 真心不容易，终于通过了。为了做这道题，将树的中序遍历和的树的创建都看了一遍，顺便看了栈和队列的实现，真的就差实现了。最后醍醐灌顶，没想到创建两个root，相当于两个一样的树，不同的使用。真的是长见识了！基本上算是用了六个小时。说明本人的数据结构学的不是很扎实，需要好好的敲打敲打，复习一下。

方法二、使用HashSet快速查找的方式

思路描述

• 遍历整棵树，对于每一个遍历到的结点，其值为value，根据value1 + value2 = target，在hashset中找寻target - value1是否在其中）
  • 如果在其中，说明存在可以构成对应的target的两个数字
  • 如果不在其中，那就将该结点的value加入hashset中。

python实现（leetcode版本）

class Solution(object):        def find(self,set,root,k):            if root == None:                return False            if k - root.val in set:                return True            else:                set.add(root.val)                return self.find(set,root.left,k) | self.find(set,root.right,k)        def findTarget(self, root, k):            hashset = set()            return self.find(hashset,root,k)

python语言的完整版（包括树的生成和遍历）

class TreeNode(object):    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right    def buildTree(self, list):        print(id(self))        self.val = list[0]        for i in range(1, len(list)):            root = self            while root != None:                if list[i] > root.val:                    if root.right != None:                        root = root.right                    else:                        temp = TreeNode(list[i], None, None)                        root.right = temp                        break                else:                    if root.left != None:                        root = root.left                    else:                        temp = TreeNode(list[i], None, None)                        root.left = temp                        break    def showTree(self):        nodeList = []        numList = []        nodeList.append(self)        while len(nodeList) != 0:            if not nodeList[0].left is None:                nodeList.append(nodeList[0].left)            if not nodeList[0].right is None:                nodeList.append(nodeList[0].right)            numList.append(nodeList[0].val)            nodeList.pop(0)        print(numList)class Solution(object):    def find(self,set,root,k):        if root == None:            return False        if k - root.val in set:            return True        else:            set.add(root.val)            return self.find(set,root.left,k) | self.find(set,root.right,k)    def findTarget(self, root, k):        hashset = set()        return self.find(hashset,root,k)        """        :type root: TreeNode        :type k: int        :rtype: bool        """if __name__ == '__main__':    root = TreeNode()    list = [5, 3, 2, 6, 4, 7]    print(id(root))    root.buildTree(list)    print("到底有没有改变",root.val)    root.showTree()    solution = Solution()    print(solution.findTarget(root,13))

分析总结

• 出现如下错误，是因为没有正确的缩进，indentation level缩进对齐
  
• 注意python中的方法传递同样是引用传递，所以不能在方法内给该引用修改地址，只能修改该地址指向的内容

总结

• 针对不同的数据结构由不同的处理方法，这些是建立在对各种数据结构很熟悉的前提之下。

  • BST中序遍历，会将的所有的数字按照升序排序，同时的BST的搜索方式也很快。
  • hashmap和hashset的形式也是完全不一样的，hashmap是键值对，主要是对key进行的hash值的运算，而hashse则是集合，仅仅是单个的元素。检索的速度远远快于的BST。但是仅仅会的使用现成的数据结构，如python中的。对于C中的，自己编写一个hash值就比较难了

• C和python的编程思想不同，注意转化。

• 虽然这道题不难，但是对于复习数据结构还是有很大的邦助的

转载地址：http://wwwvb.baihongyu.com/