653. 两数之和 IV - 输入 BST

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

二叉树的节点个数的范围是 [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int count(struct TreeNode *root) {
    
    if (root == NULL) return 0;
    return count(root->left) + count(root->right) + 1;
}

void getItem(struct TreeNode *root, int *ret) {
    
    if (root == NULL) return;
    getItem(root->left, ret);
    ret[++ret[0]] = root->val;
    getItem(root->right, ret);
    return ;
}

bool findTarget(struct TreeNode* root, int k){
    
    int n = count(root);
    int *ret = (int *)malloc(sizeof(int) * (n + 1));
    ret[0] = 0;
    getItem(root, ret);
    int l = 1, r = ret[0];
    while (l < r && ret[l] + ret[r] != k) {
    
        if (ret[l] + ret[r] < k) l++;
        else r--;
    }
    return l < r;
}