← Static tasks

1261. Find Elements in a Contaminated Binary Tree

leetcode medium

#csharp#hash-table#leetcode#medium#recursion#search#tree#two-pointers

Task

Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input

["FindElements","find","find"]

[[[-1,null,-1]],[1],[2]]

Output

[null,false,true]

C# solution

matched/original
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class FindElements {
    private HashSet<int> values = new HashSet<int>();
    public FindElements(TreeNode root) {
        root.val = 0;
        values.Add(0);
        Recover(root);
    }
    private void Recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.Add(node.left.val);
            Recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.Add(node.right.val);
            Recover(node.right);
        }
    }
    public bool Find(int target) {
        return values.Contains(target);
    }
}

C++ solution

auto-draft, review before submit
#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 x) { val = x; }
}
public class FindElements {
    private HashSet<int> values = new HashSet<int>();
    public FindElements(TreeNode root) {
        root.val = 0;
        values.push_back(0);
        Recover(root);
    }
    private void Recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.push_back(node.left.val);
            Recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.push_back(node.right.val);
            Recover(node.right);
        }
    }
    public bool Find(int target) {
        return values.Contains(target);
    }
}

Java solution

matched/original
import java.util.HashSet;
import java.util.Set;

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

public class FindElements {
    private TreeNode root;
    private Set<Integer> values = new HashSet<>();
    
    public FindElements(TreeNode root) {
        this.root = root;
        root.val = 0;
        values.add(0);
        recover(root);
    }
    
    private void recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.add(node.left.val);
            recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.add(node.right.val);
            recover(node.right);
        }
    }
    
    public boolean find(int target) {
        return values.contains(target);
    }
}

Go solution

matched/original
package main

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

type FindElements struct {
    values map[int]bool
}

func Constructor(root *TreeNode) FindElements {
    fe := FindElements{values: make(map[int]bool)}
    root.Val = 0
    fe.values[0] = true
    fe.recover(root)
    return fe
}

func (fe *FindElements) recover(node *TreeNode) {
    if node.Left != nil {
        node.Left.Val = 2*node.Val + 1
        fe.values[node.Left.Val] = true
        fe.recover(node.Left)
    }
    if node.Right != nil {
        node.Right.Val = 2*node.Val + 2
        fe.values[node.Right.Val] = true
        fe.recover(node.Right)
    }
}

func (fe *FindElements) Find(target int) bool {
    return fe.values[target]
}

Explanation

Algorithm

Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений.

😎