1214. Two Sum BSTs

LeetCode medium оригинал: C# #csharp #graph #hash-table #leetcode #medium #search #tree #two-pointers

LeetCode Static

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18

Output: false

C# решение

сопоставлено/оригинал

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 {
    private void Dfs(TreeNode node, HashSet<int> nodeSet) {
        if (node == null) return;
        Dfs(node.left, nodeSet);
        nodeSet.Add(node.val);
        Dfs(node.right, nodeSet);
    }
    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        HashSet<int> nodeSet1 = new HashSet<int>();
        HashSet<int> nodeSet2 = new HashSet<int>();
        Dfs(root1, nodeSet1);
        Dfs(root2, nodeSet2);
        
        foreach (int value1 in nodeSet1) {
            if (nodeSet2.Contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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:
    private void Dfs(TreeNode node, HashSet<int> nodeSet) {
        if (node == null) return;
        Dfs(node.left, nodeSet);
        nodeSet.push_back(node.val);
        Dfs(node.right, nodeSet);
    }
    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        HashSet<int> nodeSet1 = new HashSet<int>();
        HashSet<int> nodeSet2 = new HashSet<int>();
        Dfs(root1, nodeSet1);
        Dfs(root2, nodeSet2);
        
        foreach (int value1 in nodeSet1) {
            if (nodeSet2.Contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    private void dfs(TreeNode currNode, Set<Integer> nodeSet) {
        if (currNode == null) {
            return;
        }
        dfs(currNode.left, nodeSet);
        nodeSet.add(currNode.val);
        dfs(currNode.right, nodeSet);
    }
    
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        Set<Integer> nodeSet1 = new HashSet<>();
        Set<Integer> nodeSet2 = new HashSet<>();
        dfs(root1, nodeSet1);
        dfs(root2, nodeSet2);

        for (int value1 : nodeSet1) {
            if (nodeSet2.contains(target - value1)) {
                return true;
            }
        }
        
        return false;
    }   
}

Python решение

сопоставлено/оригинал

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

class Solution:
    def dfs(self, node, node_set):
        if not node:
            return
        self.dfs(node.left, node_set)
        node_set.add(node.val)
        self.dfs(node.right, node_set)

    def twoSumBSTs(self, root1, root2, target):
        node_set1 = set()
        node_set2 = set()
        self.dfs(root1, node_set1)
        self.dfs(root2, node_set2)
        
        for value1 in node_set1:
            if target - value1 in node_set2:
                return True
                
        return False

Go решение

сопоставлено/оригинал

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

func dfs(node *TreeNode, nodeSet map[int]struct{}) {
    if node == nil {
        return
    }
    dfs(node.Left, nodeSet)
    nodeSet[node.Val] = struct{}{}
    dfs(node.Right, nodeSet)
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
    nodeSet1 := make(map[int]struct{})
    nodeSet2 := make(map[int]struct{})
    dfs(root1, nodeSet1)
    dfs(root2, nodeSet2)
    
    for value1 := range nodeSet1 {
        if _, found := nodeSet2[target - value1]; found {
            return true
        }
    }
    
    return false
}

Algorithm

Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.