653.两数之和IV-输入BST

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

层序遍历（BFS)

维护一个set，每访问一个值就写入，当前节点值为val，当k-val存在于set时，表示存在两个节点和为k

BST在查找某个数时比较搞笑，复杂度logN，但找两数之和并不高效，复杂度On

用前序dfs遍历也可，但是会访问到叶节点，而层序bfs不一定要到叶就能找到，除非极端情况

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        s = set()   #记录访问过的节点值
        q = [root]
        while q:
            for _ in range(len(q)):
                node = q.pop(0)
                val = node.val
                if k - val in s:
                    return True
                s.add(val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return False