653. 两数之和 IV - 输入 BST

Difficulty
easy
Tags
二叉树
二叉搜索树
URL
https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
Star
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
notion imagenotion image
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：
notion imagenotion image
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
示例 3：
输入: root = [2,1,3], k = 4
输出: true
示例 4：
输入: root = [2,1,3], k = 1
输出: false
示例 5：
输入: root = [2,1,3], k = 3
输出: true
提示:
  • 二叉树的节点个数的范围是 [1, 104].
  • 104 <= Node.val <= 104
  • root 为二叉搜索树
  • 105 <= k <= 105
通过次数47,353提交次数78,682

法1 中序 + 双指针

思路
先采用中序遍历将二叉树的值保存下来，再采用双指针搜索
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        nums = []

        # 中序遍历二叉树，保存所有数字
        cur = root
        stack = []
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            
            cur = stack.pop()
            nums.append(cur.val)
            cur = cur.right

        # 双指针搜索结果
        left, right = 0, len(nums)-1
        while left < right:
            temp = nums[left] + nums[right]
            if temp == k:
                return True
            elif temp < k:
                left += 1
            else:
                right -= 1
        
        return False

法2 迭代器 + 双指针

思路
设计类似
⚙️
173. 二叉搜索树迭代器，使得该迭代器可以从左右两边都可以直接取值，然后就可以用O(h)的复杂度来搜索。
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:
    def __init__(self, root: TreeNode, forward):
        self.stack = []
        self.forward = forward
        while root:
            self.stack.append(root)
            root = root.left if self.forward else root.right
            

    def next(self) -> int:
        temp = self.stack.pop()
        res = temp.val
        # 递增的顺序
        if self.forward:
                temp = temp.right
                while temp:
                    self.stack.append(temp)
                    temp = temp.left
        # 从 右往左 递减的顺序
        else:
                temp = temp.left
                while temp:
                    self.stack.append(temp)
                    temp = temp.right
        return res

    def hasNext(self) -> bool:
        return self.stack != []

    def peek(self):
        return self.stack[-1].val

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
				# 构造 左右两个迭代器
        left =  BSTIterator(root, True)
        right = BSTIterator(root, False)
				# 采用双指针搜索
        while left.hasNext() and right.hasNext() and left.peek() != right.peek():
            temp = left.peek() + right.peek()
            if temp == k:
                return True
            elif temp > k:
                right.next()
            elif temp < k:
                left.next()
        
		return False