边工作边刷题：70天一遍leetcode: day 94-1

Largest BST Subtree

要点：

• http://articles.leetcode.com/largest-binary-search-tree-bst-in
• 这题重点是理解题意，还有道类似题 Largest Binary Search Tree (BST) in a Binary Tree – LeetCode( http://articles.leetcode.com/largest-binary-search-tree-bst-in_22
• 两题的区别：
  • 本题with all descendants：需要所有left/right子树都是bst，并且和root构成bst。而另一题是如果left or right不是bst，root还可以是（这里注意即使不要求所有descendants，结点仍需要连接的才构成bst）
  • 显然如果all descendants，需要检查到最底才能决定，所以bottom up方法。而另一题要从上到下扩展，所以top-down。
• return value和args：
  • 本题用bottom up的方法，所有min/max是return的，并且要return子树的判定状态和结点个数：-1表示子树不是bst，0个结点还是可以的。其他个数要比较min/max和root。
    • 通过检查-1/0来ignore返回的max/min：所以可以返回0/0作为max/min
  • 另一题return的个数是0或者实际个数，另外如果不能扩展了，要以这个子树为root重新计数

错误点：

• 不能因为left子树不符合就提前返回，仍然要遍历right子树来找到其他root对应的bst subtree

https://repl.it/Cb9Z/2

# 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. # Hint:# You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity. # Follow up: # Can you figure out ways to solve it with O(n) time complexity?# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def largestBSTSubtree(self, root):""":type root: TreeNode:rtype: int"""def bfs(root):if not root:return 0,0,0isBST = Trueleftnodes, maxl, minl = bfs(root.left)if leftnodes==-1 or (leftnodes!=0 and root.val<maxl):isBST = Falseif leftnodes==0:minl = root.valrightnodes, maxr, minr = bfs(root.right)if rightnodes==-1 or (rightnodes!=0 and root.val>minr):isBST = Falseif rightnodes==0:maxr = root.valif isBST:self.maxLen = max(self.maxLen, leftnodes+rightnodes+1)return leftnodes+rightnodes+1, maxr, minlreturn -1, 0, 0self.maxLen = 0bfs(root)return self.maxLen

转载于:https://www.cnblogs.com/absolute/p/5815850.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的边工作边刷题：70天一遍leetcode: day 94-1的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。