98. 验证二叉搜索树

问题98 验证二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/

如何判断一颗二叉树是不是BST呢？根据BST的定义，本质上就是判断这颗二叉树的中序遍历是不是递增的。如果是递增的，那说明这是一颗BST，如果不是递增的，则说明这不是一颗有效的BST。既然如此，那就中序遍历就可以了，笨一点的办法是将中序遍历的结果存储到一个list或stack中，无论是递归还是非递归，然后判断list或stack中元素的顺序是否符合要求。那么能不能在遍历过程中动态检查元素大小关系，从而判定是否有效的BST呢？也可以的，只不过稍微麻烦点。至于官方题解里的递归写法，确实简洁，抽时间再写一下。

使用递归：

	public boolean isValidBST(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		return inOrder(root, stack);
	}

	private boolean inOrder(TreeNode node, Stack<TreeNode> stack) {
		if (node == null) {
			return true;
		}

		if (node.left != null) {
			boolean ret = inOrder(node.left, stack);
			if (!ret) {
				return false;
			}
		}

		if (!stack.isEmpty()) {
			TreeNode last = stack.peek();
			if (node.val <= last.val) {
				return false;
			}
		}

		stack.add(node);

		if (node.right != null) {
			boolean ret = inOrder(node.right, stack);
			if (!ret) {
				return false;
			}
		}

		return true;
	}

不使用递归：

	public boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}

		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		TreeNode prev = null;
		while (node != null
			|| !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}

			TreeNode cur = stack.pop();

			if (prev != null && cur.val <= prev.val) {
				return false;
			}

			prev = cur;

			if (cur.right != null) {
				node = cur.right;
			}
		}

		return true;
	}

在 LeetCode 查看