题目大意:给你一棵二叉搜索树,返回树中是否存在两个节点的和等于给定的目标值。
Problem:
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:
1 2 3 4 5 6 7 8 9 10 |
Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True |
Example 2:
1 2 3 4 5 6 7 8 9 10 |
Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False |
Solution:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Running time: 36 ms class Solution { public: bool findTarget(TreeNode* root, int k) { vector<int> nums; inorder(root, nums); int l = 0; int r = nums.size() - 1; while (l < r) { int sum = nums[l] + nums[r]; if (sum == k) return true; else if (sum < k) ++l; else --r; } return false; } private: void inorder(TreeNode* root, vector<int>& nums) { if (root == nullptr) return; inorder(root->left, nums); nums.push_back(root->val); inorder(root->right, nums); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment