LC: 333. Largest BST Subtree
https://leetcode.com/problems/largest-bst-subtree/
333. Largest BST Subtree
Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.
A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:
The left subtree values are less than the value of their parent (root) node's value.
The right subtree values are greater than the value of their parent (root) node's value.
Note: A subtree must include all of its descendants.
Follow up: Can you figure out ways to solve it with O(n) time complexity?
Example 1:
Example 2:
Constraints:
The number of nodes in the tree is in the range
[0, 104].-104 <= Node.val <= 104
The Essence:
Nach der Definitions eines binären Suchbaums muss der Wert des Elterknotens größer als alle Werte in seinem linken Teilbaum und kleiner als alle Werte in seinem rechten Teilbaum sein. Wenn durch ein Rekursionsverfahren die Kindknoten dem Elterknoten den niedrigste und höchste Wert in dem Teilbaum zurückgibt, kann der Elterknoten kontrollieren, ob es hierbei ein binärer Suchbaum vorliegt.
Details:
In der Implementation kann die Kindknoten auch die maximale Größe eines binären Suchbaums in ihren Teilbäumen zurückgeben. Daneben kann ein Knoten als maximaler bzw. minimaler Wert positive bzw. Negative Unendlichkeit zurückgeben, wenn der Teilbaum kein binärer Suchbaum ist.
Solution(s):
Default Code:
Last updated