563. Binary Tree Tilt

LeetCode easy оригинал: C# #csharp #easy #leetcode #math #recursion #search #tree #two-pointers

LeetCode Static

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]

Output: 1

Explanation:

Tilt of node 2 : |0-0| = 0 (no children)

Tilt of node 3 : |0-0| = 0 (no children)

Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)

Sum of every tilt : 0 + 0 + 1 = 1

C# решение

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

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    private int totalTilt = 0;
    
    public int FindTilt(TreeNode root) {
        SumAndTilt(root);
        return totalTilt;
    }
    
    private int SumAndTilt(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = SumAndTilt(node.left);
        int rightSum = SumAndTilt(node.right);
        int nodeTilt = Math.Abs(leftSum - rightSum);
        totalTilt += nodeTilt;
        return node.val + leftSum + rightSum;
    }
}

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 x) { val = x; }
}
class Solution {
public:
    private int totalTilt = 0;
    
    public int FindTilt(TreeNode root) {
        SumAndTilt(root);
        return totalTilt;
    }
    
    private int SumAndTilt(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = SumAndTilt(node.left);
        int rightSum = SumAndTilt(node.right);
        int nodeTilt = abs(leftSum - rightSum);
        totalTilt += nodeTilt;
        return node.val + leftSum + rightSum;
    }
}

Java решение

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

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;
    }
}

public class Solution {
    private int totalTilt = 0;
    
    public int findTilt(TreeNode root) {
        sumAndTilt(root);
        return totalTilt;
    }
    
    private int sumAndTilt(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = sumAndTilt(node.left);
        int rightSum = sumAndTilt(node.right);
        int nodeTilt = Math.abs(leftSum - rightSum);
        totalTilt += nodeTilt;
        return node.val + leftSum + rightSum;
    }
}

JavaScript решение

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

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    findTilt(root) {
        let totalTilt = 0;
        
        function sumAndTilt(node) {
            if (node === null) {
                return 0;
            }
            const leftSum = sumAndTilt(node.left);
            const rightSum = sumAndTilt(node.right);
            const nodeTilt = Math.abs(leftSum - rightSum);
            totalTilt += nodeTilt;
            return node.val + leftSum + rightSum;
        }
        
        sumAndTilt(root);
        return totalTilt;
    }
}

Python решение

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

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

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.total_tilt = 0
        
        def sum_and_tilt(node):
            if not node:
                return 0
            left_sum = sum_and_tilt(node.left)
            right_sum = sum_and_tilt(node.right)
            node_tilt = abs(left_sum - right_sum)
            self.total_tilt += node_tilt
            return node.val + left_sum + right_sum
        
        sum_and_tilt(root)
        return self.total_tilt

Go решение

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

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

func findTilt(root *TreeNode) int {
    totalTilt := 0
    
    var sumAndTilt func(node *TreeNode) int
    sumAndTilt = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftSum := sumAndTilt(node.Left)
        rightSum := sumAndTilt(node.Right)
        nodeTilt := abs(leftSum - rightSum)
        totalTilt += nodeTilt
        return node.Val + leftSum + rightSum
    }
    
    sumAndTilt(root)
    return totalTilt
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Algorithm

Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла.

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

Верните общую сумму наклонов всех узлов.

😎

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

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

Все вакансии

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