请问BST里怎么处理“等于”的情况？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请问BST里怎么处理“等于”的情况？

请问BST里怎么处理“等于”的情况？# JobHunting - 待字闺中

n*r2013-05-01 07:05

1 楼

很多BST的题都是recursion解法
套路是分支recursive
根据BST的性质做某个比较
< 的情况往左子树延伸
> 的情况往右子树延伸或者相反
那"="的情况一般怎么处理？会造成麻烦吗？有没有哪位总结过？
比方说吧，一个BST里可能有一些节点存的data相等，然后写函数求该BST任意两个节
点的first common ancestor,但是你不知道该BST建立时遇到相等的数据的规则是存左
还是存右。这是个例子，想知道有没有什么general rules.

d*s2013-05-01 07:05

2 楼

都有，随便存哪边，insert/search一致就行

f*72013-05-01 07:05

3 楼

如果面试时遇到，那就向面试官确认他想怎么搞，如果他无所谓，那就怎么都行

【在 n********r 的大作中提到】

: 很多BST的题都是recursion解法
: 套路是分支recursive
: 根据BST的性质做某个比较
: < 的情况往左子树延伸
: > 的情况往右子树延伸或者相反
: 那"="的情况一般怎么处理？会造成麻烦吗？有没有哪位总结过？
: 比方说吧，一个BST里可能有一些节点存的data相等，然后写函数求该BST任意两个节
: 点的first common ancestor,但是你不知道该BST建立时遇到相等的数据的规则是存左
: 还是存右。这是个例子，想知道有没有什么general rules.