LC: 250. Count Univalue Subtrees
https://leetcode.com/problems/count-univalue-subtrees/
250. Count Univalue Subtrees
Given the root of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
Example 1:
Input: root = [5,1,5,5,5,null,5]
Output: 4Example 2:
Input: root = []
Output: 0Example 3:
Input: root = [5,5,5,5,5,null,5]
Output: 6Constraints:
The numbrt of the node in the tree will be in the range
[0, 1000].-1000 <= Node.val <= 1000
The Essence:
Zu beachten ist die rekursive Definition: Eine Wurzel bildet genau dann einen einwertigen Teilbaum, wenn ihre Kinder ebenfalls einwertige Teilbäume sind und ihr Wert gleich dem ihrer Kinder ist.
Wir können also die Anzahl solcher Unterbäume zählen, indem wir den Baum von Blättern angefangen durchlaufen. Zuerst soll man alsıo die Kindknoten verarbeiten, was durch Nebenreihenfolge zu machen ist. Die globale Anzahl wird jedes Mal inkrementiert, wenn die Wurzel solcher Bäume gefunden werden.
In Algorithmen, Informatik und Wissenschaft ist im Allgemeinen wichtig zu sehen, worauf die Definitionen der Begriffe hindeuten, um sie für die Problemlösung zu nutzen.
Details:
Man kann die Lösung durch Rekursion implementieren. Man kann entweder die Werte der Elterknoten zu den Kindknoten als Zahl eingeben oder das Ergebnis der Kindknoten zu den Elterknoten als Boolean zurückgeben.
Solution(s) and Further Explanation:
Default Code:
Last updated