333. Largest BST Subtree
Tree, DFS, BFS, DP, Binary Tree, AMateList ·Problem Statement
link: LeetCode.cn LeetCode 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.
Example:
Input: root = [10,5,15,1,8,null,7]
Output: 3
Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2
Constraints: The number of nodes in the tree is in the range [0, 104]. -104 <= Node.val <= 104
Follow up: Can you figure out ways to solve it with O(n) time complexity?
Solution Approach
The solution recursively checks each subtree to determine if it’s a valid BST and calculates its size, returning the size of the largest BST subtree by comparing sizes from all subtrees.
Algorithm
Check BST Validity: Use a helper function to validate if a subtree satisfies the BST properties by ensuring all node values are within a specified range.
Count Nodes in BST: If a subtree is a valid BST, use another helper function to count the number of nodes in that subtree.
Compare Subtree Sizes: Recursively check all subtrees of the root, and track the size of the largest valid BST subtree encountered.
Complexity
time complexity: O(n) space complexity: O(h)
Implement
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:
def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
def count_node(root):
if not root:
return 0
cnt = 1
return cnt + count_node(root.left) + count_node(root.right)
def check_bst(root, lower, upper):
if not root:
return True
if root.val <= lower or root.val >= upper:
return False
return check_bst(root.left, lower, min(upper, root.val)) and \
check_bst(root.right, max(lower, root.val), upper)
def dfs(root):
if check_bst(root, -100000, 100000):
return count_node(root)
return max(dfs(root.left), dfs(root.right))
return dfs(root)