LeetCode（Binary Search Tree)653. Two Sum IV - Input is a BST

Love The Way You Lie 2023-09-26 20:39 106阅读 0赞

# 1.问题 #

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Example 1:  
![在这里插入图片描述][54cb6e80b33e46a891461f3588366bb1.png]

> Input: root = \[5,3,6,2,4,null,7\], k = 9  
> Output: true

Example 2:  
![在这里插入图片描述][74dd575afd5e42808edc800d53d0f657.png]

> Input: root = \[5,3,6,2,4,null,7\], k = 28  
> Output: false

Constraints:

*  The number of nodes in the tree is in the range \[1, 104\].
 *  104 <= Node.val <= 104
 *  root is guaranteed to be a valid binary search tree.
 *  105 <= k <= 105

# 2. 解题思路 #

## 方法1： ##

> BST 中序遍历得到的是升序排列的节点值  
> 1.先进行中序遍历  
> 2,将得到的节点值存储到一个列表中  
> 3.最后再用双指针的方式查找是否存在两个节点的值之和等于目标值。  
> 具体来说，使用两个指针，一个指向列表的起始位置，一个指向列表的末尾位置，然后不断移动指针，直到找到满足条件的两个节点或者指针相遇为止。  
> 时间复杂度为 O(n)，其中 n 是 BST 的节点数。

## 方法2： ##

> 1.前序遍历二叉树，并将遍历到的节点值添加到List集合中  
> 2.循环List集合中的节点值，使用双指针方法查找是否存在两个节点值的和等于k  
> 3.如果存在两个节点值的和等于k，则返回true,否则返回false

## 方法3： ##

> 利用哈希表的思想  
> 1.遍历整棵树并将遍历过的节点值存入一个Set集合中  
> 2.每次遍历到一个节点时，判断Set集合中是否存在目标值与该节点值之差（即k-root.val）  
> 3.若存在则说明找到了符合条件的两个节点，返回true；否则将当前节点值加入Set集合中，并递归查找左右子树。  
> 4.如果遍历整棵树都没有找到符合条件的节点，返回false。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public boolean findTarget(TreeNode root, int k) {
        
            // 使用List存储BST的中序遍历结果
            List<Integer> list = new ArrayList<>();
            inorder(root, list);
            
            // 使用双指针在中序遍历结果中查找两数之和为k
            int left = 0, right = list.size() - 1;
            while (left < right) {
        
                int sum = list.get(left) + list.get(right);
                if (sum == k) {
        
                    return true;
                } else if (sum < k) {
        
                    left++;
                } else {
        
                    right--;
                }
            }
            return false;
        }
    
        // 递归中序遍历BST，将结果存储到List中
        private void inorder(TreeNode root, List<Integer> list) {
        
            if (root == null) {
        
                return;
            }
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

## 代码2： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean findTarget(TreeNode root, int k) {
        
            // 创建一个List集合，用于存储遍历二叉树后的节点值
            List<Integer> list = new ArrayList<>();
            // 遍历二叉树，并将遍历到的节点值添加到List集合中
            preorder(root,list);
            // 循环List集合中的节点值，使用双指针方法查找是否存在两个节点值的和等于k
            for(int i=0;i<list.size()-1;i++){
        
                for(int j=i+1;j<list.size();j++){
        
                    if(list.get(i)+list.get(j)==k){
        
                        // 如果存在两个节点值的和等于k，则返回true
                        return true;                   
                    }
                }
            }
            // 如果不存在两个节点值的和等于k，则返回false
            return false;     
        }  
        // 前序遍历二叉树，并将遍历到的节点值添加到List集合中
        public void preorder(TreeNode root,List<Integer> list){
        
             if(root==null) {
        
                 return;
             }
             list.add(root.val);
             preorder(root.left,list);
             preorder(root.right,list);
        }
    }

> 是上面代码的优化

class Solution {
        
        public boolean findTarget(TreeNode root, int k) {
        
            List<Integer> list = new ArrayList<>();
            preorder(root, list);
            if (list.size() <= 1) {
        
                return false;
            }
            for (int i = 0; i < list.size(); i++) {
        
                int res = list.get(i);
                int target = k - res;
                if (list.indexOf(target) > i && list.contains(target)) {
        
                  return true;
                 }
            }
            return false;
        }
    
        public void preorder(TreeNode root, List<Integer> list) {
        
            if (root == null) {
        
                return;
            }
            list.add(root.val);
            preorder(root.left, list);
            preorder(root.right, list);
        }
    }

> 注释：

if (list.contains(k-res)) {
        
                    return true;
                }

> 之前代码一直认为没问题，但运行错误  
> 错误的原因：一个节点的值最多只能出现一次，因此 list.contains(k-res) 可能会导致结果错误。  
> 若 k=10，那么 findTarget(root, k) 应该返回 true，但是上述代码会返回 false，因为 2 和 4 的值都是 2，list.contains(8) 的结果为 false。  
> 因此，在判断是否存在 k - res 的元素时，需要避免重复判断，可以通过判断其索引是否大于 i 来实现

5
       / \
      3   6
     / \   \
    2   4   7

for (int i = 0; i < list.size(); i++) {
        
                int res = list.get(i);
                int target = k - res;
                if (list.indexOf(target) > i && list.contains(target)) {
        
                  return true;
                 }
            }

## 代码3： ##

class Solution {
        
        // 定义一个Set集合用于存储遍历过的节点值
        Set<Integer> res = new HashSet<>();
    
        public boolean findTarget(TreeNode root, int k) {
        
            // 如果节点为空，返回false
            if (root == null) {
        
                return false;
            }
            // 如果Set集合中存在k-root.val的值，则返回true
            if (res.contains(k - root.val)) {
        
                return true;
            }
            // 将当前节点值添加到Set集合中
            res.add(root.val);
            // 递归查找左右子树
            return findTarget(root.left, k) || findTarget(root.right, k);
        }
    }

[54cb6e80b33e46a891461f3588366bb1.png]: https://img-blog.csdnimg.cn/54cb6e80b33e46a891461f3588366bb1.png
[74dd575afd5e42808edc800d53d0f657.png]: https://img-blog.csdnimg.cn/74dd575afd5e42808edc800d53d0f657.png