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。 : 只有中序是的。
|