687. Longest Univalue Path

LeetCode medium original: C# #csharp #leetcode #math #medium #recursion #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 корень бинарного дерева, return длину самого длинного пути, на котором все узлы имеют одинаковое значение. Этот путь может проходить через корень или не проходить.

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

Exemple:

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

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

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

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

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

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

😎

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.