原題：兩數(shù)之和 IV - 輸入 BST
方法一：
中序遍歷，有序存放到一個數(shù)組中，通過兩數(shù)之和 II - 輸入有序數(shù)組(golang)即可解。
func findTarget(root *TreeNode, k int) bool {
arr := DFS(root)
for l, r := 0, len(arr)-1; l < r; {
sum := arr[l] + arr[r]
if sum < k {
l ++
} else if sum > k {
r --
} else {
return true
}
}
return false
}
func DFS(node *TreeNode) []int {
// 左根右
if node == nil {
return []int{}
}
arr := DFS(node.Left)
arr = append(arr, node.Val)
arr = append(arr, DFS(node.Right)...)
return arr
}
方法二：
類似兩數(shù)之和(golang)使用map存儲已經(jīng)遍歷過結(jié)點值
func findTarget(root *TreeNode, k int) bool {
m := make(map[int]bool)
return DFS(root, k, m)
}
func DFS(node *TreeNode, k int, m map[int]bool) bool {
if node == nil {
return false
}
if _, ok := m[k-node.Val]; ok {
return true
}
m[node.Val] = true
if DFS(node.Left, k, m) || DFS(node.Right, k, m) {
return true
}
return false
}
