二叉搜索树判定

二叉搜索树BST：任意节点的值一定大于其左子树中的每一个节点的值，并小于其右子树中的每一个节点的值。

1.中序遍历的方法

---

1）对树进行中序遍历，将结果保存在数组中；

2）检测数组是否为升序排列，如果是，则为BST，反之则不是。

进一步优化，为避免使用额外的内存开销，不使用数组。在中序遍历时定义preNode保存前驱节点，如果当前节点小于等于前驱节点，则该树不是BST。

---

2.思路简单，但效率低

对树中的每个节点，判断左子树的最大值小于当前根节点的值，右子树的最小值大于当前根节点的值，即为BST。

因需要重复遍历树中的部分数据，故效率较低。

---

3.思维逻辑太过简单，不严谨。即错误。

对于每个节点，判断它的左孩子节点是否小于它，且右孩子节点是否大于它。

忽略了很严重的问题：每棵子树可能保证左<根<右，但并不能保证整棵树的所有左<根<所有右。如[10,5,15,null,null,6,20]。