w**h
发帖数: 34 | 1 白
谈research;
什么是binary search tree?
如何validate a BST? 写code，给了递归解法；
follow-up, 如何用非递归方法解决这个问题，coding;
问问题。 |
n*******w
发帖数: 687 | |
q****x
发帖数: 7404 | 3 非递归解法是啥？用栈实现中序周游？
【在 w**h 的大作中提到】
: 白
: 谈research;
: 什么是binary search tree?
: 如何validate a BST? 写code，给了递归解法；
: follow-up, 如何用非递归方法解决这个问题，coding;
: 问问题。
|
A**u
发帖数: 2458 | 4 你运气太好了。。。
cong
第三题目这里有方法， method 4 in order
http://www.geeksforgeeks.org/archives/3042
http://www.leetcode.com/2010/04/binary-search-tree-in-order-tra
【在 w**h 的大作中提到】
: 白
: 谈research;
: 什么是binary search tree?
: 如何validate a BST? 写code，给了递归解法；
: follow-up, 如何用非递归方法解决这个问题，coding;
: 问问题。
|
s******n
发帖数: 3946 | |
n*******w
发帖数: 687 | 6 非递归的话，中序比较好写，但是并不graceful。
另外可以设计个数据结构，用先序后序遍历也行。 |
s******n
发帖数: 3946 | 7 展开说说用先序？
【在 n*******w 的大作中提到】
: 非递归的话，中序比较好写，但是并不graceful。
: 另外可以设计个数据结构，用先序后序遍历也行。
|
s******n
发帖数: 3946 | 8 先序想不出来，后序：每个节点保存子树的最大最小值，后序遍历先访问两个字节点，
再判断node->left->Max < node.value < node->left->Min; |
n*******w
发帖数: 687 | 9 这样做复杂度是O(n^2)。
比较好的方法是top-down。用min max，递归实现在这里。
http://www.leetcode.com/2010/09/determine-if-binary-tree-is-bin
http://www.mitbbs.com/article_t/JobHunting/31990685.html
如果非递归先序后序做，也是这个思路。
需要改动的是，栈的结构变成，
stack{
Node n;
int min, max;
}
出栈的时候除了得到n，还得refresh min max。
递归中序，需要保留前一个遍历过的节点的值。
referennce或者pointer实现。其实容易错。
【在 s******n 的大作中提到】
: 先序想不出来，后序：每个节点保存子树的最大最小值，后序遍历先访问两个字节点，
: 再判断node->left->Max < node.value < node->left->Min;
|
q****x
发帖数: 7404 | 10 先根很容易啊。
【在 n*******w 的大作中提到】
: 这样做复杂度是O(n^2)。
: 比较好的方法是top-down。用min max，递归实现在这里。
: http://www.leetcode.com/2010/09/determine-if-binary-tree-is-bin
: http://www.mitbbs.com/article_t/JobHunting/31990685.html
: 如果非递归先序后序做，也是这个思路。
: 需要改动的是，栈的结构变成，
: stack{
: Node n;
: int min, max;
: }
|
|
|
n*******w
发帖数: 687 | 11 嗯，这个思路，先序后序并没有本质区别。
【在 q****x 的大作中提到】
: 先根很容易啊。
|
q****x
发帖数: 7404 | 12 非递归先序和中序，记住之前一个节点值，应该最简单。
【在 n*******w 的大作中提到】
: 嗯，这个思路，先序后序并没有本质区别。
|
n*******w
发帖数: 687 | 13 先序不一样啊。从栈pop出来，前一个值并不是predecessor。
只有中序是的。
【在 q****x 的大作中提到】
: 非递归先序和中序，记住之前一个节点值，应该最简单。
|
g*****i
发帖数: 2162 | |
q****x
发帖数: 7404 | 15 中序测bst
【在 n*******w 的大作中提到】
: 先序不一样啊。从栈pop出来，前一个值并不是predecessor。
: 只有中序是的。
|
