687. Longest Univalue Path

LeetCode medium original: C# #csharp #leetcode #math #medium #recursion #tree #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

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

Example:

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

matched/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

auto-draft, review before submit

#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

matched/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

matched/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

matched/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

matched/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

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.