653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True

Example 2:

Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False

思路：将二叉树中序遍历转换为排序数组，然后O(N)遍历

void Inorder(TreeNode* root, vector<int>& nums){ if (!root)return; Inorder(root->left, nums); nums.push_back(root->val); Inorder(root->right, nums); } bool findTarget(TreeNode* root, int k) { if (!root)return false; vector<int> res; Inorder(root, res); int low = 0, high = res.size() - 1; while (low < high){ if (res[low] + res[high] > k)high--; else if (res[low] + res[high] < k)low++; else return true; } return false; }