判断二叉搜索树

灰太狼 2022-04-15 01:06 176阅读 0赞

二叉查找树（Binary Search Tree），（又：[二叉搜索树][Link 1]，二叉排序树）它或者是一棵空树，或者是具有下列性质的[二叉树][Link 2]： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为[二叉排序树][Link 3]。

判断某棵树是否为二叉搜索树

单纯判断每个结点比左孩子大比右孩子小是不对的。如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

15推翻了这种方法。

思路：

1）可以根据定义判断，递归进行，如果左右子树都为搜索二叉树，且左子树最大值小于根，右子树最小值大于根。成立。

2）根据定义，中序遍历为递增序列，我们中序遍历后判断是否递增即可。

3）我们可以在中序遍历过程中判断之前节点和当前结点的关系，不符合直接返回false即可。

4）进一步通过morris遍历优化

morris遍历：[https://blog.csdn.net/hebtu666/article/details/83093983][https_blog.csdn.net_hebtu666_article_details_83093983]

public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    	public static boolean isBST(Node head) {
    		if (head == null) {
    			return true;
    		}
    		boolean res = true;
    		Node pre = null;
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			}
    			if (pre != null && pre.value > cur1.value) {
    				res = false;
    			}
    			pre = cur1;
    			cur1 = cur1.right;
    		}
    		return res;
    	}

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879
[Link 3]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/10905079
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220415/381273b0aa054c6f9e3f3f28b908be19.png
[https_blog.csdn.net_hebtu666_article_details_83093983]: https://blog.csdn.net/hebtu666/article/details/83093983