563. Binary Tree Tilt

LeetCode easy original: C# #csharp #easy #leetcode #math #recursion #search #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

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

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

Ví dụ:

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ời giải

đã khớp/gố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++ 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.
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ời giải

đã khớp/gốc

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ời giải

đã khớp/gốc

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ời giải

đã khớp/gốc

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ời giải

đã khớp/gốc

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

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.