563. Binary Tree Tilt

LeetCode easy original: C# #csharp #easy #leetcode #math #recursion #search #tree #two-pointers
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

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

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

Beispiel:

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# Lösung

zugeordnet/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++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

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

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.