文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個二叉搜索樹和一個目標結果，如果 BST 中存在兩個元素且它們的和等于給定的目標結果，則返回 true。

案例 1: 輸入: 5/ \3 6/ \ \ 2 4 7Target = 9 輸出: True案例 2: 輸入: 5/ \3 6/ \ \ 2 4 7Target = 28 輸出: False

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 創建二叉搜索樹的正向和反向迭代器（中序是排好序的），一個從前面開始，一個從后面開始
• 雙指針逼近給定的數即可

相關參考：LeetCode 173. 二叉搜索樹迭代器（中序遍歷）

class Solution {TreeNode *begin, *end, *temp;stack<TreeNode*> s1, s2; public:bool findTarget(TreeNode* root, int k) {if(root == NULL)return false;begin = end = root;TreeNode *i = next(), *j = prev();while(i != j){if(i->val+j->val > k)j = prev();//和大了，j減小else if(i->val+j->val < k)i = next();//和小了，i增大else//if(i->val+j->val == k)return true;}return false;}TreeNode* next()//正向迭代器，從最小的開始{while(begin){s1.push(begin);begin = begin->left;}temp = s1.top();s1.pop();begin = temp->right;return temp;}TreeNode* prev()//反向迭代器，從最大的開始{while(end){s2.push(end);end = end->right;}temp = s2.top();s2.pop();end = temp->left;return temp;} };

總結

以上是生活随笔為你收集整理的LeetCode 653. 两数之和 IV - 输入 BST（二叉搜索树迭代器双指针）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。