今天是一道简单题，来看题目LeetCode 653. 两数之和 IV - 输入 BST

题目

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例

示例1：

1 2	输入: root = [5,3,6,2,4,null,7], k = 9 输出: true

示例2：

1 2	输入: root = [5,3,6,2,4,null,7], k = 28 输出: false

题解

题目很简单，一看就懂。

先简单介绍一下BST，BST是满足以下三个条件的二叉树：

节点的左子树包含的节点的值小于该节点的值
节点的右子树包含的节点的值大于等于该节点的值
节点的左子树和右子树都是BST

接下来介绍两种解法。

BST特性：中序遍历 + 双指针

因为是BST，所以直接使用中序遍历能够转换成有序数组，进而能够使用双指针。

先把整个二叉树通过中序遍历加入到数组 nums 中，然后对其用双指针 nums[l] + nums[r] 计算出值与 k 对比大小:

如果 nums[l] + nums[r] > k 则 r--
如果 nums[l] + nums[r] < k 则 l++
如果 nums[l] + nums[r] == k 则 return true

代码

// 执行 32 ms 超越 81.55%  消耗 35.9 MB 超越 75.94%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> nums;
    bool findTarget(TreeNode* root, int k) {
        BSTout(root);
        int l=0,r=nums.size()-1;
        for(int i:nums)
            cout<<i<<endl;
        while(l!=r)
        {
            if(nums[l]+nums[r]>k)
                r--;
            if(nums[l]+nums[r]<k)
                l++;
            if(l!=r&&nums[l]+nums[r]==k)
                return true;
        }
        return false;
    }
    void BSTout(TreeNode* root)
    {
        if(root==nullptr)
            return;
        BSTout(root->left);
        nums.push_back(root->val);
        BSTout(root->right);
    }
};

暴力：二叉树遍历 + hash 判断

直接对二叉树遍历，然后将其加入set中,如果发现 set.find(k - val)!=map.end() 成立,则直接 return ture,反之遍历完二叉树后 return false，十分简单粗暴。

代码

// 执行 36 ms 超越 67.15%  消耗 37.8 MB 超越 36.32%
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    set<int> nums;
    bool findTarget(TreeNode* root, int k) {
        if(root==nullptr)
            return false;
        if(nums.find(k-root->val)!=nums.end())
            return true;
        nums.insert(root->val);
        return findTarget(root->left,k) || findTarget(root->right,k);
    }
};