j**********3
发帖数: 3211 | 1 我用最直接的方法，把他们都存到数组里，然后从左到右扫一遍。。。找到顺序乱的。。
但这个方法space o(n)
有啥好主意？还想到了用俩pointer那个方法，但这个不知道是否可行。。。 |
g****o
发帖数: 547 | 2 啥意思?
存到数组里后找longest increasing subsequence? |
s********l
发帖数: 998 | 3 最大bst是说个数最多吗？
我觉得不用extra space把~
从底向上 返回每个node下 最大bst的个数 要是
有新的最大值就更新max
这样应该可以把~ |
j**********3
发帖数: 3211 | 4 对的
我知道这个办法并不好
【在 g****o 的大作中提到】
: 啥意思?
: 存到数组里后找longest increasing subsequence?
|
j**********3
发帖数: 3211 | 5 好像可以哦。。
楼主说的第二个方法可以么？
【在 s********l 的大作中提到】
: 最大bst是说个数最多吗？
: 我觉得不用extra space把~
: 从底向上 返回每个node下 最大bst的个数 要是
: 有新的最大值就更新max
: 这样应该可以把~
|
i**********u
发帖数: 119 | |
j**********3
发帖数: 3211 | 7 其实不需要存，是吧？
【在 i**********u 的大作中提到】
: 中序遍历 最长递增序列
|
a***a
发帖数: 739 | 8 Time: O(n), Space: O(1)应该能作到.
with Poster-Order process, recursively call on the left/right children,
which returns:
1. The largest BST size in this branch
2. The largest BST size in this branch starting with the root
3. The value range [min, max] of the BST in (2)
Based on this information returned from left/right children, the current
root can easily figure out the things it needs to return itself. |
h***k
发帖数: 161 | 9 recursion is never space O1, except tail recursion
【在 a***a 的大作中提到】
: Time: O(n), Space: O(1)应该能作到.
: with Poster-Order process, recursively call on the left/right children,
: which returns:
: 1. The largest BST size in this branch
: 2. The largest BST size in this branch starting with the root
: 3. The value range [min, max] of the BST in (2)
: Based on this information returned from left/right children, the current
: root can easily figure out the things it needs to return itself.
|
