本文共 812 字,大约阅读时间需要 2 分钟。
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 7Target = 9Output: True
Example 2:
Input: 5 / \ 3 6 / \ \2 4 7Target = 28Output: False
思路:将二叉树中序遍历转换为排序数组,然后O(N)遍历
void Inorder(TreeNode* root, vector & 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 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;}
转载地址:http://uaxei.baihongyu.com/