LeetCode 653. Two Sum IV


题目描述
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
tag
k-sum题 二叉树 二叉搜索树
样例
1 | 输入: |
算法
(哈希表) O(n)
思路
复杂度分析
最多树中每个节点遍历一遍。
python 代码
1 | class : |
算法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 代码