（js）leetcode 653. 两数之和 IV - 输入 BST

旧城等待， 2022-12-25 06:53 105阅读 0赞

### 题目： ###

> 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
> 
> 案例 1:
> 
> 输入:   
>     5  
>    / \\  
>   3   6  
>  / \\   \\  
> 2   4   7
> 
> Target = 9
> 
> 输出: True  
>  
> 
> 案例 2:
> 
> 输入:   
>     5  
>    / \\  
>   3   6  
>  / \\   \\  
> 2   4   7
> 
> Target = 28
> 
> 输出: False

### 思路： ###

> 1. 遍历整棵树，在树的每个节点上遍历它的左子树和右子树
> 
> 2. 对于每一个值为 p 的节点，在 set 中检查是否存在 k-p
> 
>     1）存在，则可以在该树上找到两个和为 k 的节点
> 
>     2）否则，将 p 放入 set 中
> 
> 3. 若遍历了整棵树之后，没有两个节点的和为 k ，则不存在这样的两个节点

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} k
     * @return {boolean}
     */
    var findTarget = function(root, k) {
        let set = new Set();
        return find(root, k, set)
    };
    
    var find = function(root, k, set) {
        if(root == null) {
            return false;
        }
        if(set.has(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221120/9b3d6f9cdf5c4a769d7ec0b020a71520.png