666. Path Sum IV

LeetCode medium original: C# #array #csharp #graph #hash-table #leetcode #medium #tree #two-pointers
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
LeetCode Static

Если глубина дерева меньше 5, то это cây можно представить в виде mảngа трехзначных чисел. Для каждого числа в этом mảngе:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.

Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.

Единицы представляют значение v этого узла, где 0 <= v <= 9.

Дан mảng возрастающих трехзначных чисел nums, представляющих бинарное cây с глубиной меньше 5. return сумму всех путей от корня к листьям.

Гарантируется, что данный mảng представляет собой валидное связанное бинарное cây.

Ví dụ

Input: nums = [113,215,221]

Output: 12

Explanation: The tree that the list represents is shown.

The path sum is (3 + 5) + (3 + 1) = 12.

C# lời giải

đã khớp/gốc 
public class Solution {
    public int PathSum(int[] nums) {
        var tree = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(Dictionary<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.ContainsKey(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.ContainsKey(leftChild) && !tree.ContainsKey(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int PathSum(vector<int>& nums) {
        var tree = new unordered_map<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(unordered_map<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.count(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.count(leftChild) && !tree.count(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

Java lời giải

đã khớp/gốc 
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int pathSum(int[] nums) {
        Map<Integer, Integer> tree = new HashMap<>();
        
        for (int num : nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree.put(depth * 10 + pos, val);
        }
        
        return dfs(tree, 1, 1, 0);
    }
    
    private int dfs(Map<Integer, Integer> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.containsKey(key)) {
            return 0;
        }
        currentSum += tree.get(key);
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.containsKey(leftChild) && !tree.containsKey(rightChild)) {
            return currentSum;
        }
        return dfs(tree, depth + 1, 2 * pos - 1, currentSum) + dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

JavaScript lời giải

đã khớp/gốc 
var pathSum = function(nums) {
    let tree = new Map();
    
    for (let num of nums) {
        let depth = Math.floor(num / 100);
        let pos = Math.floor(num / 10) % 10;
        let val = num % 10;
        tree.set(depth * 10 + pos, val);
    }
    
    return dfs(tree, 1, 1, 0);
};

function dfs(tree, depth, pos, currentSum) {
    let key = depth * 10 + pos;
    if (!tree.has(key)) {
        return 0;
    }
    currentSum += tree.get(key);
    let leftChild = (depth + 1) * 10 + 2 * pos - 1;
    let rightChild = (depth + 1) * 10 + 2 * pos;
    if (!tree.has(leftChild) && !tree.has(rightChild)) {
        return currentSum;
    }
    return dfs(tree, depth + 1, 2 * pos - 1, currentSum) + dfs(tree, depth + 1, 2 * pos, currentSum);
}

Go lời giải

đã khớp/gốc 
func pathSum(nums []int) int {
    tree := make(map[int]int)
    
    for _, num := range nums {
        depth := num / 100
        pos := (num / 10) % 10
        val := num % 10
        tree[depth*10+pos] = val
    }
    
    return dfs(tree, 1, 1, 0)
}

func dfs(tree map[int]int, depth, pos, currentSum int) int {
    key := depth*10 + pos
    if _, exists := tree[key]; !exists {
        return 0
    }
    currentSum += tree[key]
    leftChild := (depth + 1) * 10 + 2*pos - 1
    rightChild := (depth + 1) * 10 + 2*pos
    if _, leftExists := tree[leftChild]; !leftExists && !tree[rightChild] {
        return currentSum
    }
    return dfs(tree, depth+1, 2*pos-1, currentSum) + dfs(tree, depth+1, 2*pos, currentSum)
}

Algorithm

Создание структуры дерева:

Пройдите по mảngу nums и для каждого elementа создайте узел дерева.

Сохраните узлы в словаре для удобного доступа по их позиции.

Связывание узлов:

Пройдите по mảngу и свяжите узлы друг с другом, исходя из их позиции и глубины.

find левого и правого ребенка для каждого узла и установите соответствующие связи.

Подсчет суммы путей:

Выполните обход дерева (наVí dụ, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm
Chưa có việc làm đang hoạt động.