687. Longest Univalue Path

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

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

Ví dụ:

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

đã khớp/gốc

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

đã khớp/gốc

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

đã khớp/gốc

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

đã khớp/gốc

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

đã khớp/gốc

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

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.