思路和算法

中序遍历得到的值一定是升序的，所以我们只要在遍历的时候实时地检查当前元素是否大于上一个遍历的值(lastNum),如果小于或等于，可直接得出不是二叉搜索树的结论。用栈来模拟中序便利的过程。

实现代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { if(root == null){ return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; Integer lastNum = null; while(!stack.isEmpty() || cur != null){ while(cur != null){ stack.push(cur); cur = cur.left; } cur = stack.pop(); if(lastNum != null && cur.val <= lastNum){ return false; } lastNum = cur.val; cur = cur.right; } return true; } }

细节:利用Integer包装类来保留上一次遍历到的值

复杂度分析

时间复杂度O(n):n为二叉树的节点个数，每个节点最多被访问一次。

空间复杂度O(n):栈最多存储 nn 个节点，因此需要额外的 O(n)O(n) 的空间。