563. Binary Tree Tilt

LeetCode easy original: C# #csharp #easy #leetcode #math #recursion #search #tree #two-pointers
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
LeetCode Static

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

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

Ejemplo:

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# solución

coincidente/original 
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++ solución

borrador automático, revisar antes de enviar 
#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 solución

coincidente/original 
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 solución

coincidente/original 
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 solución

coincidente/original 
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 solución

coincidente/original 
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

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

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

return общую сумму наклонов всех узлов.

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.