LeetCode 653. Two Sum IV

发表于  |  分类于 前端  |  没有评论

题目描述

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

tag

k-sum题 二叉树 二叉搜索树

样例

1
2
3
4
5
6
7
8
9
10
 
输入: 
    5
   / 
  3   6
 /    
2   4   7

Target = 9

输出: True

算法

(哈希表) O(n)
思路
复杂度分析

最多树中每个节点遍历一遍。

python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class :
    def findTarget(self, root: TreeNode, k: int) -> bool:
        stack = [root]
        table = set()
        while stack:
            node = stack.pop()
            if node:
                if k - node.val in table:
                    return True
                else:
                    table.add(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return False

算法2

(双指针)
思路

类似在数组中的双指针操作，但是在本题BST中。l += 1的操作变成BST在中序遍历序列中的下一个更大元素，r -= 1的操作变成上一个更小元素。

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106071/Iterative-solution-with-O(n)-time-O(logn)-space-with-detailed-explanation.-Only-traverse-the-binary-tree-once!!!-time-O(logn)-space-with-detailed-explanation.-Only-traverse-the-binary-tree-once!!!)

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106086/Two-Pointer-on-BST-Solution-using-generator-in-python-(O(n)-time-O(logn)-space-if-BST-is-balanced)-time-O(logn)-space-if-BST-is-balanced))

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/299778/Python-Stack-based-two-pointer-DFS-solution-O(n)-time-O-(log-n)-space-for-balanced-trees-time-O-(log-n)-space-for-balanced-trees)

复杂度分析
python 代码

上一篇: LeetCode 190. Reverse Bits

下一篇: LeetCode 17. Letter Combinations of a Phone Number