简单

64

相关企业

给定一个二叉搜索树的 根节点 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 的节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> temp = new LinkedList<>();
        dfs(root, temp);
        int left = 0;
        int right = temp.size() - 1;
        while(left <right){
            if(temp.get(left) + temp.get(right) == k){
                return true;
            }
            if(temp.get(left) + temp.get(right) < k){
                left++;
            }
            if(temp.get(left) + temp.get(right) > k){
                right --;
            }
        }
        return false;
    }
    void dfs(TreeNode root, List<Integer> temp){
        if(root == null) return;
        dfs(root.left, temp);
        temp.add(root.val);
        dfs(root.right,temp);
    }
}