https://leetcode.com/problems/validate-binary-search-tree/description/
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3 Binary tree [2,1,3] , return true.
Example 2:
1 / \ 2 3 Binary tree [1,2,3] , return false.
思路：搜索二叉树的中序遍历会输出从小到大的序列
package go.jacob.day805; import java.util.Stack; public class Demo1 { /* * 方法一：利用二叉树的中序遍历 */ public boolean isValidBST(TreeNode root) { if (root == null) return true; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; TreeNode pre = null; while (!stack.isEmpty() || cur != null) { if (cur == null) { cur = stack.pop(); if (pre != null && pre.val >= cur.val) return false; pre = cur; cur = cur.right; } else { stack.push(cur); cur = cur.left; } } return true; } private class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }
