2-Sum Binary Tree

• Time : O(nlogn)
• Space : O(1)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
int search(TreeNode* node, int n, int l, int r) {
    if(!node) return 0;
    if(node->val == n) return 1;
    if(l <= n and n <= r) {
        return search(node->left, n, l, node->val - 1) or search(node->right, n, node->val + 1, r);
    }
    return 0;
}
int dfs(TreeNode* node, int sum, TreeNode* root) {
    if(!node) return 0;
    int n = sum - node->val;
    if(n != node->val and search(root, n, INT_MIN, INT_MAX)) return 1;
    return dfs(node->left, sum, root) or dfs(node->right, sum, root);
}
int Solution::t2Sum(TreeNode* A, int B) {
    return dfs(A,B,A);
}