【树】653. 两数之和 IV - 输入 BST

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void inorder_traversal(TreeNode* node, vector<int>& nums)
13     {
14         if (node == nullptr)
15         {
16             return;
17         }
18 
19         inorder_traversal(node->left, nums);
20         nums.push_back(node->val);
21         inorder_traversal(node->right, nums);
22     }
23 
24 
25     bool findTarget(TreeNode* root, int k) 
26     {
27 
28         vector<int> nums;
29         inorder_traversal(root, nums);
30 
31         int left = 0;
32         int right = nums.size() - 1;
33 
34         while (left < right)
35         {
36             int sum = nums.at(left) + nums.at(right);
37             if (sum == k)
38             {
39                 return true;
40             }
41             else if (sum > k)
42             {
43                 --right;
44             }
45             else
46             {
47                 ++left;
48             }
49         }
50 
51         return false;
52     }
53 };