### 题目描述 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。 ### 输入输出 #### 示例1  ``` 输入: root = [5,3,6,2,4,null,7], k = 9 输出: true ``` ### 题目解答 寻找2个数字之和，想法还是采用记录的方式达到O(n)的时间复杂度。对于二叉搜索树，采用中序遍历的方式，也就是由小到大访问节点。访问成功后，我们就将该节点放入集合中。每个节点访问的时候，都去集合里面查看是否由k-val的节点在集合中，如果有那么就说明存在和为k的。 算法复杂度：一次访问节点，复杂度O(N) #### 代码实现 ```python class Solution: def findTarget(self, root: Optional[TreeNode], k: int) -> bool: sets = set() def midOrder(root): if root is None: return False res1 = midOrder(root.left) sets.add(root.val) if k - root.val in sets and root.val * 2 != k: return True res2 = midOrder(root.right) return res1 or res2 return midOrder(root) ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复