298. Binary Tree Longest Consecutive Sequence

LeetCode medium оригинал: C# #csharp #graph #leetcode #math #medium #recursion #tree #two-pointers

LeetCode Static

Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений.

Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути.

Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути.

Пример:

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

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

C# решение

сопоставлено/оригинал

public class Solution {
    private int maxLength = 0;
    public int LongestConsecutive(TreeNode root) {
        Dfs(root, null, 0);
        return maxLength;
    }
    private void Dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) return;
        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = Math.Max(maxLength, length);
        Dfs(node.left, node, length);
        Dfs(node.right, node, length);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 maxLength = 0;
    public int LongestConsecutive(TreeNode root) {
        Dfs(root, null, 0);
        return maxLength;
    }
    private void Dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) return;
        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = max(maxLength, length);
        Dfs(node.left, node, length);
        Dfs(node.right, node, length);
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    private int maxLength = 0;

    public int longestConsecutive(TreeNode root) {
        dfs(root, null, 0);
        return maxLength;
    }

    private void dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) return;
        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = Math.max(maxLength, length);
        dfs(node.left, node, length);
        dfs(node.right, node, length);
    }
}

JavaScript решение

сопоставлено/оригинал

class Solution {
    constructor() {
        this.maxLength = 0;
    }

    longestConsecutive(root) {
        this.dfs(root, null, 0);
        return this.maxLength;
    }

    dfs(node, parent, length) {
        if (!node) return;
        if (parent && node.val === parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        this.maxLength = Math.max(this.maxLength, length);
        this.dfs(node.left, node, length);
        this.dfs(node.right, node, length);
    }
}

Python решение

сопоставлено/оригинал

class Solution:
    def __init__(self):
        self.maxLength = 0

    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.dfs(root, None, 0)
        return self.maxLength

    def dfs(self, node: Optional[TreeNode], parent: Optional[TreeNode], length: int) -> None:
        if not node:
            return
        if parent and node.val == parent.val + 1:
            length += 1
        else:
            length = 1
        self.maxLength = max(self.maxLength, length)
        self.dfs(node.left, node, length)
        self.dfs(node.right, node, length)

Go решение

сопоставлено/оригинал

package main

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

type Solution struct {
    maxLength int
}

func (sol *Solution) longestConsecutive(root *TreeNode) int {
    sol.dfs(root, nil, 0)
    return sol.maxLength
}

func (sol *Solution) dfs(node *TreeNode, parent *TreeNode, length int) {
    if node == nil {
        return
    }
    if parent != nil && node.Val == parent.Val+1 {
        length++
    } else {
        length = 1
    }
    if length > sol.maxLength {
        sol.maxLength = length
    }
    sol.dfs(node.Left, node, length)
    sol.dfs(node.Right, node, length)
}

Algorithm

Инициализация и начало обхода:

Начните обход дерева с корневого узла.

Инициализируйте переменную length, чтобы хранить текущую длину последовательного пути, и передавайте её вниз по дереву.

Сравнение текущего узла с родительским узлом:

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

Если значение текущего узла на единицу больше значения родительского узла, увеличьте length.

Если значение текущего узла не является последовательным (не больше на единицу), сбросьте length на 1.

Обход дерева:

Рекурсивно обходите левое и правое поддерево, передавая обновлённое значение length.

В каждом узле обновляйте максимальную длину последовательного пути, если текущая длина больше.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.