原文链接 [链接] Description: 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 gi ..

[每日 LeetCode] 653. Two Sum IV - Input is a BST

本贴最后更新于 281 天前,其中的信息可能已经事过境迁

原文链接 [每日 LeetCode] 653. Two Sum IV - Input is a BST

Description:

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

思路:本题要求二叉搜索树下的两数之和。还是采用转化的策略,把树中的元素转化为数组求解。这里有一个特殊之处,二叉搜索树的中序遍历结果肯定是从小到大有序的,有序数组可使用双指针法查找是否存在两数之和。


C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> vec;
        inorder(root,vec);
        for(int i=0, j=vec.size()-1; i<j;){
            if (vec[i] + vec[j] == k)
                return true;
            (vec[i] + vec[j] < k) ? ++i: --j;
        }
        return false;
    }
    void inorder(TreeNode* root, vector<int> & vec)
    {
        if(!root)    
            return ;
        inorder(root->left,vec);
        vec.push_back(root->val);
        inorder(root->right,vec);
    } 
};

运行时间:44ms

运行内存:25.1M

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    164 引用 • 61 回帖
  • Tree
    35 引用 • 6 回帖
  • Easy
    101 引用 • 10 回帖
回帖
请输入回帖内容...