[第二轮] 3/11-3/17 CareerCup 4.5

Implement a function to check if a binary tree is a binary searchtree.

发帖规范:http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

initial: flag=1
when traversing a binary tree, if the value of left node is greater than the parent node or the value of right is smaller than the parent node, flag=0; break the recursion. Here, 'parent' means all parents nodes...  My poor english...

my gist:https://gist.github.com/sing1ee/5135093

Recursively check each node with its children if it has any, while updating the upper bound and lower bound of possible value its children in a BST should have.
https://github.com/moophis/careercup/blob/master/4.5.cpp

EchoMemory 发表于 2013-3-11 16:19
initial: flag=1
when traversing a binary tree, if the value of left node is greater than the parent ...

It is not the whole story. You should consider more scenarios.

first method： recursive， keep tracking min and max value when traverse down the sub tree
                       Time O(n), space O(1);

second method: in order traverse the tree and keep tracking previous node and current node
                       Time O(n), space O(n);

https://gist.github.com/chrislukkk/5174594

moophis 发表于 2013-3-15 19:33
It is not the whole story. You should consider more scenarios.

I knew what you mean. Thx for reminder, I edited it again. Sorry for adding confusion, I described the solution too brief and unclear...

https://gist.github.com/ThunderXu/5176045
use recursion, for each node compare it with the max value of its left sub-tree and the min value of its right sub-tree

recursively check whether the left<middle<right value holds at each node

c++ implementation, see function bool isBST()

https://github.com/StanleyLee/CareerCup/blob/master/4_1.cpp

https://github.com/1094401996/Ca ... fourdot5/IsBST.java

好吧，自己写出递归的感觉还是不错的。。。。不过似乎方法恶心了点。。。下周再优化一下。。。

每次感觉顶不下去的时候就看看地里编程算法面试题板块越来越少的跟帖。。。。。那么多人已经放弃了，，，，我还没有。。。有点小阴暗 继续坚持下去。。。