算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 最大 BST 子树,我们先来看题面:
https://leetcode-cn.com/problems/largest-bst-subtree/
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.
给定一个二叉树,找到其中最大的二叉搜索树(BST)子树,其中最大指的是子树节点数最多的。
注意:
子树必须包含其所有后代。
示例:
输入: [10,5,15,1,8,null,7]
10
/ \
5 15
/ \ \
1 8 7
输出: 3
解释: 高亮部分为最大的 BST 子树。
返回值 3 在这个样例中为子树大小。
class Solution:
def largestBSTSubtree(self, root: TreeNode) -> int:
self.res = 0
def isValid(root, t1, t2):
if not root:
return 0
if root.val >= t2 or root.val <= t1:
return float("-inf")
return 1 + isValid(root.left, t1, root.val) + isValid(root.right, root.val, t2)
def helper(root):
if not root:
return
self.res = max(self.res, isValid(root,float("-inf"), float("inf")) )
helper(root.left)
helper(root.right)
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。