LC: 298. Binary Tree Longest Consecutive Sequence
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
298. Binary Tree Longest Consecutive Sequence
Given the root of a binary tree, return the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).
Example 1:
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.Example 2:
Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.Constraints:
The number of nodes in the tree is in the range
[1, 3 * 104].-3 * 104 <= Node.val <= 3 * 104
Binary Tree Longest Consecutive Sequence
The Essence:
Die Intuition für dieses Problem ist eigentlich sehr einfach und von der rekursiven Struktur des Binärbaums entstehend. Wenn ein Elterknoten bei seinen Kindknoten fortlaufende Folgen hat, soll hier die längste Folge weiter für den Elterknoten ausgewählt werden. Wenn die Folge nicht fortlaufend ist, dann können wir ihre Länge einfach als 0 annehmen.
Details:
Ob die Folgen fortlaufend sind, können wir dadurch kontrollieren, dass wir die Werte der Elter- und Kindknoten vergleichen. Man kann die Kindknoten die Werte ihrer Eltern eingeben oder die Elterknoten die Werte ihrer Kinder zurückgeben. In dem Basisfall sollen die Blätter des Baums 1 zurückgeben. Durch Addition zu der Längen und Vergleich wird die längsten Folge am Ende bestimmt. Die Traversierung soll hier der Nebenreihenfolge (L-R–N) entsprechen.
Solution(s) and Further Explanation:
Default Code:
Last updated