目录

0653:两数之和 IV - 输入二叉搜索树

力扣第 653 题

题目

给定一个二叉搜索树 root 和一个目标结果 k,如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果,则返回 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

相似问题:

分析

类似 0001,边遍历边用哈希存储元素值,每轮查询前面是否有对应的数即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def findTarget(self, root: TreeNode, k: int) -> bool:
    stack, vis = [root], set()
    while stack:
        node = stack.pop()
        if node:
            if k - node.val in vis:
                return True
            vis.add(node.val)
            stack.extend([node.right, node.left])
    return False

64 ms