题目描述

给一个数，问有给定的二叉搜索树，有没有两个数相加的和等于这个数

我的解法——暴力遍历+二分搜索

dfs遍历二叉树固定为第一个数，然后在利用BST平衡性质找另一个数
两层循环，nlogn的复杂度。
结果：beat 2.68%

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):      
    def findOther(self,now,cant,num):
        if(now is None):
            return False
        if(now.val == num and now != cant):
            return True
        else:
            return(self.findOther(now.left,cant,num) or self.findOther(now.right,cant,num))
        
    def myFindTarget(self,now,k):
        if(now is None):
            return False
        return (self.findOther(self.ROOT,now,k - now.val) or self.myFindTarget(now.left,k) or self.myFindTarget(now.right,k))
            
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        self.ROOT = root
        return self.myFindTarget(root,k)

简便解法1——转换为数组+双指针搜索

**最好的方法！！ **
先中序遍历BST树，得到从小到大的递增数列 list。然后用Sum Two的算法搞定。
一层循环，n的复杂度

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List < Integer > list = new ArrayList();
        inorder(root, list);
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int sum = list.get(l) + list.get(r);
            if (sum == k)
                return true;
            if (sum < k)
                l++;
            else
                r--;
        }
        return false;
    }
    public void inorder(TreeNode root, List < Integer > list) {
        if (root == null)
            return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

简便解法2——利用set搜索

遍历BST，将BST中的数存到set中，再遍历一次，每次从上次存好的遍历结果中找k-p
时间复杂度n

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set < Integer > set = new HashSet();
        return find(root, k, set);
    }
    public boolean find(TreeNode root, int k, Set < Integer > set) {
        if (root == null)
            return false;
        if (set.contains(k - root.val))
            return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}

参考答案

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/