題目難度: 簡單

原題鏈接

今天繼續更新 Leetcode 的劍指 Offer（專項突擊版）系列, 大家在公眾號 算法精選 里回復 劍指offer2 就能看到該系列當前連載的所有文章了, 記得關注哦~

題目描述

給定一個二叉搜索樹的 根節點 root 和一個整數 k , 請判斷該二叉搜索樹中是否存在兩個節點它們的值之和等于 k 。假設二叉搜索樹中節點的值均唯一。

示例 1：

• 輸入: root = [8,6,10,5,7,9,11], k = 12
• 輸出: true
• 解釋: 節點 5 和節點 7 之和等于 12

示例 2：

• 輸入: root = [8,6,10,5,7,9,11], k = 22
• 輸出: false
• 解釋: 不存在兩個節點值之和為 22 的節點

提示：

• 二叉樹的節點個數的范圍是 [1, 10^4].
• -10^4 <= Node.val <= 10^4
• root 為二叉搜索樹
• -10^5 <= k <= 10^5

題目思考

1. 如何利用二叉搜索樹的性質?

解決方案

思路

• 分析題目, 一個很容易想到的思路就是中序遍歷, 將二叉搜索樹轉換成一個有序數組, 存儲遞增的值
• 這樣就把問題轉換成了經典的有序數組兩數之和問題, 之前我們也做過類似的題目劍指 Offer 57. 和為 s 的兩個數字, 為了方便起見, 我把對應的思路也貼在這里了:
• 將兩個下標 i 和 j 初始化為數組的頭和尾, 然后往中間靠攏
• 根據當前的和, 具體分為以下三種情況:
  1. nums[i] + nums[j] == k: 找到一對滿足條件的數字了, 直接返回 true
  2. nums[i] + nums[j] < k: 當前和小于 k, 因為數組有序, 如果保留 nums[i], 而 j 繼續往左的話, 新的和肯定更小于 k, 所以 nums[i]可以被安全排除, 即 i 直接加 1
  3. nums[i] + nums[j] > k: 當前和大于 k, 因為數組有序, 如果保留 nums[j], 而 i 繼續往右的話, 新的和肯定更大于 k, 所以 nums[j]可以被安全排除, 即 j 直接減 1
• 這樣遍歷下去最終肯定 i 和 j 會相遇, 此時退出循環, 說明沒找到滿足條件的數字對, 返回 false 即可
• 下面代碼中有詳細的注釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 中序遍歷每個節點一遍, 雙指針遍歷每個值一遍
• 空間復雜度 O(N): 額外有序數組存儲所有節點的值

代碼

class Solution:def findTarget(self, root: TreeNode, k: int) -> bool:# 中序遍歷+雙指針# 先用中序遍歷將二叉搜索樹轉換成有序數組nums = []def inorder(node):if not node:returninorder(node.left)nums.append(node.val)inorder(node.right)inorder(root)# 然后對有序數組進行雙指針遍歷, 檢查是否存在和為k的數字對i, j = 0, len(nums) - 1while i < j:sm = nums[i] + nums[j]if sm == k:return Trueelif sm < k:i += 1else:j -= 1return False

---

大家可以在下面這些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎專欄

我的頭條號

我的牛客網博客

我的公眾號: 算法精選, 歡迎大家掃碼關注~😊