题目描述

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.
给定一个二叉搜索树和一个目标数，检查二叉搜索树中是否存在两个元素使其和等于给定的目标数。

样例

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

思路

根据题目要求，要注意是两个元素的和构成目标数，不可以是一个元素自己等于目标数，或者一个元素自己加自己等于目标数。

方法1 暴力求解

遍历树，对于每个子节点检查是否有另一个节点跟它的和为目标数。

复杂度分析

时间复杂度 $O(n^2)$ 空间复杂度 $O(1)$

因为对于每个节点都要遍历一次树，所以时间复杂度比较高。

class Solution {
public:
   bool searchBST(TreeNode* root, TreeNode* cur, int k) {
        if (cur == NULL) 
            return false;
        TreeNode*p=root;
        while(p!=NULL)
        {
            if (k == 2 * cur->val) 
                break;
            if (k == cur->val + p->val) {
                return true;
            }
            if (k > cur->val + p->val) 
                p = p->right;
            else if (k < cur->val + p->val) 
                p = p->left;
        }       
        return (searchBST(root, cur->left, k) || searchBST(root, cur->right, k));
    }

    bool findTarget(TreeNode* root, int k) {
        return searchBST(root,root,k);
    }
};

算法2 利用BST树排序节点

首先将所有节点顺序取出来，将排序好的二叉树变成一个线性的排好序的队列，然后从数组两端向中间寻找可以满足条件的搭配。

复杂度分析

最坏情况相当于将所有节点遍历了两次，因此是O(n)的复杂度。

时间复杂度 $O(n)$ 空间复杂度 $O(n)$

C++ 代码

class Solution {
public:
    vector<int> treeNode;
    void InOrder(TreeNode*root)
    {
        if(root==NULL)
            return;
        InOrder(root->left);
        treeNode.push_back(root->val);
        InOrder(root->right);
    }

    bool findTarget(TreeNode* root, int k) {
        InOrder(root);
        int l=0;
        int r=treeNode.size()-1;
        while(l!=r)
        {
            int sum=treeNode[l]+treeNode[r];
            if(sum==k)
                return true;
            else if(sum>k)
                r--;
            else if(sum<k)
                l++;
        }
        return false;
    }
};