563. Binary Tree Tilt

LeetCode easy original: C# #csharp #easy #leetcode #math #recursion #search #tree #two-pointers
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

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

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

Exemple:

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# solution

correspondant/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++ solution

brouillon automatique, à relire avant soumission 
#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 solution

correspondant/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 solution

correspondant/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 solution

correspondant/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 solution

correspondant/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 общую сумму наклонов всех узлов.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.