肏屄免费,亚洲高潮在线观看,成人性生交大免费看,97色色综合网,91精品国产专区,小黄片网址,天天操夜夜撸,亚洲1区2区3区4区5区

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做 最大 BST 子樹(shù)，我們先來(lái)看題面：

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.

給定一個(gè)二叉樹(shù)，找到其中最大的二叉搜索樹(shù)（BST）子樹(shù)，其中最大指的是子樹(shù)節(jié)點(diǎn)數(shù)最多的。

注意:

子樹(shù)必須包含其所有后代。

示例

示例:

輸入: [10,5,15,1,8,null,7]

   10 
   / \ 
  5  15 
 /  \    \ 
1   8   7

輸出: 3
解釋: 高亮部分為最大的 BST 子樹(shù)。
     返回值 3 在這個(gè)樣例中為子樹(shù)大小。

解題

思路一：判斷每個(gè)節(jié)點(diǎn)是否是二叉搜索樹(shù)

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)