687. Longest Univalue Path

LeetCode medium original: C# #csharp #leetcode #math #medium #recursion #tree #two-pointers
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
LeetCode Static

given корень бинарного дерева, return длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить.

Длина пути между двумя узлами представлена количеством рёбер между ними.

Esempio:

Input: root = [5,4,5,1,1,null,5]

Output: 2

Explanation: The shown image shows that the longest path of the same value (i.e. 5).

C# soluzione

abbinato/originale 
public class Solution {
    private int ans = 0;
    private int Solve(TreeNode root, int parent) {
        if (root == null) {
            return 0;
        }
        int left = Solve(root.left, root.val);
        int right = Solve(root.right, root.val);
        
        ans = Math.Max(ans, left + right);
        
        return root.val == parent ? Math.Max(left, right) + 1 : 0;
    }
    public int LongestUnivaluePath(TreeNode root) {
        Solve(root, -1);
        return ans;
    }
}

C++ soluzione

bozza automatica, rivedere prima dell'invio 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int ans = 0;
    private int Solve(TreeNode root, int parent) {
        if (root == null) {
            return 0;
        }
        int left = Solve(root.left, root.val);
        int right = Solve(root.right, root.val);
        
        ans = max(ans, left + right);
        
        return root.val == parent ? max(left, right) + 1 : 0;
    }
    public int LongestUnivaluePath(TreeNode root) {
        Solve(root, -1);
        return ans;
    }
}

Java soluzione

abbinato/originale 
class Solution {
    private int ans = 0;

    private int solve(TreeNode root, int parent) {
        if (root == null) {
            return 0;
        }

        int left = solve(root.left, root.val);
        int right = solve(root.right, root.val);
        
        ans = Math.max(ans, left + right);
        
        return root.val == parent ? Math.max(left, right) + 1 : 0;
    }

    public int longestUnivaluePath(TreeNode root) {
        solve(root, -1);
        return ans;
    }
}

JavaScript soluzione

abbinato/originale 
class Solution {
    constructor() {
        this.ans = 0;
    }

    solve(root, parent) {
        if (!root) return 0;

        const left = this.solve(root.left, root.val);
        const right = this.solve(root.right, root.val);
        
        this.ans = Math.max(this.ans, left + right);
        
        return root.val === parent ? Math.max(left, right) + 1 : 0;
    }

    longestUnivaluePath(root) {
        this.solve(root, -1);
        return this.ans;
    }
}

Python soluzione

abbinato/originale 
class Solution:
    def __init__(self):
        self.ans = 0

    def solve(self, root, parent):
        if not root:
            return 0
        
        left = self.solve(root.left, root.val)
        right = self.solve(root.right, root.val)
        
        self.ans = max(self.ans, left + right)
        
        return max(left, right) + 1 if root.val == parent else 0

    def longestUnivaluePath(self, root):
        self.solve(root, -1)
        return self.ans

Go soluzione

abbinato/originale 
package main

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

type Solution struct {
    ans int
}

func (s *Solution) solve(root *TreeNode, parent int) int {
    if root == nil {
        return 0
    }

    left := s.solve(root.Left, root.Val)
    right := s.solve(root.Right, root.Val)
    
    if s.ans < left+right {
        s.ans = left + right
    }
    
    if root.Val == parent {
        if left > right {
            return left + 1
        } else {
            return right + 1
        }
    }
    return 0
}

func (s *Solution) LongestUnivaluePath(root *TreeNode) int {
    s.solve(root, -1)
    return s.ans
}

Algorithm

Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte
Non ci sono ancora offerte attive.