剑指 Offer II 056. 二叉搜索树中两个节点之和
给定一个二叉搜索树的 根节点 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, 104].-104 <= Node.val <= 104root 为二叉搜索树-105 <= k <= 105
注意：本题与主站 653 题相同： https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 7.4 MB, 提交时间: 2022-05-26 15:33:12
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTarget(root *TreeNode, k int) bool {
var ans []int
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
ans = append(ans, node.Val)
inorder(node.Right)
}
inorder(root)
left, right := 0, len(ans)-1
for left < right { // 双指针
if ans[left] + ans[right] < k {
left++
} else if ans[left] + ans[right] > k {
right--
} else {
return true
}
}
return false
}