# LeetCode Easy653中兩數之和輸入為BST的示例分析
## 問題描述回顧
LeetCode第653題"Two Sum IV - Input is a BST"題目描述如下：
給定一個二叉搜索樹(BST)和一個目標數值`k`，判斷BST中是否存在兩個節點，其節點值之和等于給定的`k`。
示例1：
輸入:
5
/
3 6
/ \
2 4 7
k = 9
輸出: true
示例2：
輸入:
5
/
3 6
/ \
2 4 7
k = 28
輸出: false
## 解題思路分析
### 方法一：哈希表輔助的中序遍歷
**核心思想**：利用BST中序遍歷的有序性，結合哈希表記錄已訪問節點值。
```python
def findTarget(root, k):
visited = set()
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
if k - curr.val in visited:
return True
visited.add(curr.val)
curr = curr.right
return False
時間復雜度：O(n)，每個節點訪問一次
空間復雜度：O(n)，最壞情況存儲所有節點值
實現步驟： 1. 中序遍歷得到有序數組 2. 使用雙指針在有序數組中查找兩數之和
def findTarget(root, k):
nums = []
def inorder(node):
if not node: return
inorder(node.left)
nums.append(node.val)
inorder(node.right)
inorder(root)
left, right = 0, len(nums)-1
while left < right:
total = nums[left] + nums[right]
if total == k:
return True
elif total < k:
left += 1
else:
right -= 1
return False
時間復雜度：O(n)中序遍歷 + O(n)雙指針 = O(n)
空間復雜度：O(n)存儲中序序列
# 用例1：存在解
"""
5
/ \
3 6
/ \ \
2 4 7
"""
root1 = TreeNode(5)
root1.left = TreeNode(3)
root1.right = TreeNode(6)
root1.left.left = TreeNode(2)
root1.left.right = TreeNode(4)
root1.right.right = TreeNode(7)
assert findTarget(root1, 9) == True
# 用例2：無解
assert findTarget(root1, 28) == False
# 用例3：空樹
assert findTarget(None, 0) == False
# 用例4：單節點樹
root2 = TreeNode(1)
assert findTarget(root2, 1) == False
# 用例5：重復值情況
"""
2
/ \
1 2
"""
root3 = TreeNode(2)
root3.left = TreeNode(1)
root3.right = TreeNode(2)
assert findTarget(root3, 4) == True
利用BST的搜索特性，對每個節點x，在BST中搜索k-x：
def findTarget(root, k):
def search(node, target):
if not node: return False
if node.val == target: return True
return search(node.left, target) if target < node.val else search(node.right, target)
def dfs(node):
if not node: return False
if search(root, k - node.val) and (k - node.val) != node.val:
return True
return dfs(node.left) or dfs(node.right)
return dfs(root)
時間復雜度分析：
最壞情況O(nlogn)（平衡BST）到O(n2)（退化成鏈表）
適用場景：當BST高度較低時效率較高
// 哈希表法
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet<>();
return find(root, k, set);
}
private boolean find(TreeNode node, int k, Set<Integer> set) {
if (node == null) return false;
if (set.contains(k - node.val)) return true;
set.add(node.val);
return find(node.left, k, set) || find(node.right, k, set);
}
// 雙指針法
bool findTarget(TreeNode* root, int k) {
vector<int> nums;
inorder(root, nums);
int left = 0, right = nums.size()-1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == k) return true;
sum < k ? left++ : right--;
}
return false;
}
void inorder(TreeNode* node, vector<int>& nums) {
if (!node) return;
inorder(node->left, nums);
nums.push_back(node->val);
inorder(node->right, nums);
}
# 找出所有可能的解對
def findAllPairs(root, k):
res = []
visited = set()
def traverse(node):
if not node: return
if k - node.val in visited:
res.append([k-node.val, node.val])
visited.add(node.val)
traverse(node.left)
traverse(node.right)
traverse(root)
return res
本文詳細分析了LeetCode 653題的多種解法，通過BST的特性優化算法效率。關鍵要點包括：
最終建議：在面試場景推薦使用哈希表法，因其實現簡潔且時間復雜度穩定；在內存敏感環境可考慮雙指針法。
本文共計約2150字，通過多種代碼示例和詳細分析，全面解析了BST中兩數之和問題的解決方案。讀者可根據實際需求選擇適合的算法實現。 “`
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
