653. Two Sum IV - Input is a BST

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public bool FindTarget(TreeNode root, int k) {
        HashSet<int> seen = new HashSet<int>();
        return Find(root, k, seen);
    }
    private bool Find(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) return false;
        if (seen.Contains(k - node.val)) return true;
        seen.Add(node.val);
        return Find(node.left, k, seen) || Find(node.right, k, seen);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public bool FindTarget(TreeNode root, int k) {
        HashSet<int> seen = new HashSet<int>();
        return Find(root, k, seen);
    }
    private bool Find(TreeNode node, int k, HashSet<int> seen) {
        if (node == null) return false;
        if (seen.Contains(k - node.val)) return true;
        seen.push_back(node.val);
        return Find(node.left, k, seen) || Find(node.right, k, seen);
    }
}

import java.util.HashSet;
import java.util.Set;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        return find(root, k, seen);
    }

    private boolean find(TreeNode node, int k, Set<Integer> seen) {
        if (node == null) return false;
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        return find(node.left, k, seen) || find(node.right, k, seen);
    }
}

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var findTarget = function(root, k) {
    const seen = new Set();
    function find(node) {
        if (!node) return false;
        if (seen.has(k - node.val)) return true;
        seen.add(node.val);
        return find(node.left) || find(node.right);
    }
    return find(root);
};

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findTarget(root, k):
    def find(node, k, seen):
        if not node:
            return False
        if k - node.val in seen:
            return True
        seen.add(node.val)
        return find(node.left, k, seen) or find(node.right, k, seen)
    
    return find(root, k, set())

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    return find(root, k, seen)
}

func find(node *TreeNode, k int, seen map[int]bool) bool {
    if node == nil {
        return false
    }
    if seen[k-node.Val] {
        return true
    }
    seen[node.Val] = true
    return find(node.Left, k, seen) || find(node.Right, k, seen)
}

Algorithm

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9

Output: true

👨‍💻

Алгоритм:

Выполните обход BST и сохраните все значения узлов в набор.

Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎