题目:判断一个棵树是否是BST树
思路:BST树要求当前节点的所有左子树的节点的key小于当前节点的key,右子树节点的key大于当前节点的key。例如
二叉树{10,5,#,#,15,6,20},其判断过程是这样:
1.到达key=10的节点,min=INT_MIN, max=INT_MAX, min<10<max,继续
2.到达key=5的节点,min=INT_MIN,max=10, min<5<max,继续
3.到达key=15的节点,min=10, max=INT_MAX, min<15<max,继续
4.到达key=6的节点,min=10,max=15, 不满足min<6<max,返回false
由此可见,把当前节点作为最大值传给左子树,作为最小值......
阅读全文