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

2016-10-14 约 231 字预计阅读 1 分钟次阅读

力扣第 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, 10⁴].
-10⁴ <= Node.val <= 10⁴
题目数据保证，输入的 root 是一棵有效的二叉搜索树
-10⁵ <= k <= 10⁵

分析

类似 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

目录

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

题目

分析

解答