Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note: A subtree must include all of its descendants.
Here's an example:
10
/
5 15
/
1 8 7
- The Largest BST Subtree in this case is the highlighted one.
- The return value is the subtree's size, which is 3.
Follow up: Can you figure out ways to solve it with O(n) time complexity?
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.largest_num = 0
def recu(root):
if not root: return True, 0, None, None
left_isBST, left_BST_num, left_min, left_max = recu(root.left)
right_isBST, right_BST_num, right_min, right_max = recu(root.right)
if not left_isBST or not right_isBST:
return False, None, None, None
if (left_max is None or left_max < root.val) and (right_min is None or right_min > root.val):
num = left_BST_num + right_BST_num + 1
self.largest_num = max(self.largest_num, num)
if left_min is None: left_min = root.val
if right_max is None: right_max = root.val
return True, num, left_min, right_max
return False, None, None, None
recu(root)
return self.largest_num
Summary:
- from bottom to up
LeetCode: 333. Largest BST Subtree
近期评论