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.
刚开始看到这道题有点不知道从何下手,后来看了一个三哥的讲解视频才搞定,不得不说三哥的讲解视频很不错,https://www.youtube.com/watch?v=wGXB9OWhPTg, 虽说职场三哥三姐的一些事情不便评价,但他们好的东西绝对好毫不手软地拿来学习。
联系之前也遇到过的一些bst的题,我们常常要用到的方法逃不开in order, pre order, post order traverse, iteration搞不定就上recursion,然后需要在遍历的过程中纪录和动态更新一些值来得到最后的结果。
另外对于BST的题目,刚开始分析和DP类似,要开始找一些pattern, 因为程序最后写出来会对每一个node适应,所以我们要针对每一个node总结出一套pattern, 类似于算法中的某一种证明方式,名字我忘了,这样才可以对于每一个点遍历完毕得出结果。
这道题的核心思想是,post order, 左右中,为什么呢?因为一个subtree要包含它的所有孩子结点,所以一个subtree是否是BST要先看它的所有subtree, 然后每个结点维护一个信息,isBST, size, min and max. 之后只需要考虑3种情况,
1. left & right all are isBST, 如果root也满足要求,则把root update.
2. left || right is not BST, 那么就把root 设成false, 然后更新size为left和right最小的。
3. root为空。
还有一个要注意的地方,基本常识啊,返回的若是object, 那么类型要设置成* object_Type, 因为object返回值不是premitive type, 所以是返回一个地址。
Subscribe to:
Post Comments (Atom)
Leetcode 316. Remove Duplicate Letters
这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...
-
首先声明一下,这里的面试题主要所指数据结构和算法的题目,题目的分析集中在Leetcode上面的题目上。 我认为一道面试题由以下几个方面组成的 Question Data structure in question Data structure in solutio...
-
Given an array A of integer with size of n( means n books and number of pages of each book) and k people to copy the book. You must distribu...
-
1166. Design File System Medium 62 4 Add to List Share You are asked to design a file system which provides two functions: crea...
No comments:
Post a Comment