653. 两数之和 IV - 输入 BST - 《leetcode每日一题》

1.题目
2.思路

1.题目

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

提示:

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

2.思路

1)中序遍历+双指针
看到题目首先想到的就是中序遍历二叉搜索树，获得一个递增的数组，然后利用双指针判断是否存在这样的数对。

2）dsf+哈希表
对每一个节点遍历，利用哈希表存储遍历的节点的值，对于节点root，判断哈希表中是否存在k-root->val的存在，如果有则为true，否则为false。

3）迭代+中序遍历+双指针
由想法1）拓展获得。对获得的递增数组进行的双指针遍历相当于在二叉树上直接遍历，最初的时候将指针分别指向二叉树的最左端和最右端的节点left和right，判断left->val和right->val之和与k的大小：
left->val+right->val == k 返回true；
left->val+right->val > k,更新左端节点。获得left父节点的右子树的最左端节点（当不存在右子树，返回父节点；存在右子树，但没有左节点返回右子树节点）
left->val+right->val < k,更新右端节点。获得right父节点的左子树的最右端节点（当不存在左子树，返回父节点；存在左子树，但没有右节点返回左子树节点）
3.代码
```cpp /**
- 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 dfs(TreeNode root){
```
if(root == NULL)
    return;
dfs(root->left);
record.emplace_back(root->val);
dfs(root->right);
return;
```
  } bool findTarget(TreeNode* root, int k) {
```
dfs(root);
int left = 0,right = record.size()-1;
while(left < right)
{
    int temp = record[left] + record[right];
    //cout << temp << endl;
    if(temp == k)
        return true;
    if(temp > k)
    {
        right--;
    }
    else
    {
        left++;
    }
}
return false;
```
  }

private: vector record; };

```cpp
/**
 * 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> hashtable;
    bool findTarget(TreeNode* root, int k) {
        if(root == NULL)
            return false;
        if(hashtable.count(k-root->val))
            return true;
        hashtable.insert(root->val);
        return findTarget(root->left,k)||findTarget(root->right,k);
    }
};

/**
 * 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:
    TreeNode* getleft(stack<TreeNode*>& left)
    {
        TreeNode* l = left.top();
        left.pop();
        TreeNode* ans = l->right;
        while(ans != NULL)
        {
            left.emplace(ans);
            ans = ans ->left;
        }
        return left.top();
    }

    TreeNode* getright(stack<TreeNode*>& right)
    {
        TreeNode* r = right.top();
        right.pop();
        TreeNode* ans = r->left;
        while(ans != NULL)
        {
            right.emplace(ans);
            ans = ans ->right;
        }
        return right.top();
    }

    bool findTarget(TreeNode* root, int k) {
        TreeNode* left = root;TreeNode* right = root;
        stack<TreeNode*> leftstack, rightstack;

        while(left != NULL)
        {
            leftstack.emplace(left);
            left = left->left;
        }

        while(right != NULL)
        {
            rightstack.emplace(right);
            right = right->right;
        }


        left = leftstack.top(); 
        right = rightstack.top(); 
        while(left != right)
        {
            if(left->val + right->val == k)
                return true;
            if(left->val + right->val < k)
            {
                left = getleft(leftstack);
            }
            else
            {
                right = getright(rightstack);
            }
        }
        return false;
    }
};

653. 两数之和 IV - 输入 BST

1.题目

2.思路

1)中序遍历+双指针

2）dsf+哈希表

3）迭代+中序遍历+双指针

3.代码