two-sum-iv-input-is-a-bST

Two Sum IV - Input is a BST – LeetCode 653

Problem

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.

Answer

Original

Code

/**
 * 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 {
private:
    unordered_set<int> m;
public:
    bool findTarget(TreeNode* root, int k) {
        if(root){
            if(m.count(k - root->val))
                return true;
            else{
                m.insert(root->val);
                return findTarget(root->left, k) || findTarget(root->right, k);
            }
        } else 
            return false;
    }
};

思路

简单的BFS查找，使用set进行统计。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$24$ ms，排名$33.13\%$

Better

思路

使用BFS优化递归。