[数据结构与算法]LeetCode 653.两数之和Ⅳ-输入BST C++

题目描述

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

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

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

示例 3：

输入: root = [2,1,3], k = 4
输出: true

示例 4：

输入: root = [2,1,3], k = 1
输出: false

示例 5：

输入: root = [2,1,3], k = 3
输出: true
?

提示:

二叉树的节点个数的范围是??[1, 104].
-104?<= Node.val <= 104
root?为二叉搜索树
-105?<= k <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst

解题思路

利用二叉搜索树的特性：当前结点的左孩子<当前结点<当前结点的右孩子
所以用中序遍历，并且把搜索到的结点存到数组中。这样数组中的元素就是按升序排的。
然后我们用双指针来指，一个指向头，一个指向尾。
1.如果当前两数之和=题目中的值，返回true
2.如果当前两数之和<题目中的值，i++
3.如果当前两数之和>题目中的值，j--
如果全部扫完了，全都没扫到适合的，我们就返回false

代码

/**
 * 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:
    void inOrder(TreeNode* root, vector<int> &v){
        if(root==NULL){//中序遍历，把遍历到的结点的值存到数组中
            return ;
        }
        inOrder(root->left,v);
        v.push_back(root->val);
        inOrder(root->right,v);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> v;//用来存数的数组
        inOrder(root, v);//中序遍历，并且存入数组
        int i=0;//指向头
        int j=v.size()-1;//指向尾
        while(i<j){//一个在左，一个在右直接扫
            if(v[i]+v[j]==k){//如果相加的值==k，说明找到了
                return true;
                break;
            }
            if(v[i]+v[j]<k){//如果小了，i++
                i++;
            }
            if(v[i]+v[j]>k){//如果大了，j--
                j--;
            }
        }
        return false;//扫完了，没找到，返回fasle
    }
};