298. Binary Tree Longest Consecutive Sequence

leetcode medium

#csharp#graph#leetcode#math#medium#recursion#tree#two-pointers

Task

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

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

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

Пример:

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

matched/original

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

matched/original

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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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)
}

Explanation

Algorithm

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

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

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

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

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

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

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

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

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

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

😎