687. Longest Univalue Path

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

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

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

Ejemplo:

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

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

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

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

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

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.