给定一个二叉树根节点,请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
例:
图1
图2
数据范围:节点数量满足 ,节点上的值满足
/* * function TreeNode(x) { * this.val = x; * this.left = null; * this.right = null; * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ function isValidBST(root) { // 1. 初始化变量 // 栈数组 const stack = []; // 游标 current let current = root; // 记录前一个节点 let pre = null; while (stack.length > 0 || current !== null) { // 1. 中序遍历的套路 不断遍历 把游标的节点加入栈 if (current) { stack.push(current); // 2. 不断遍历左子树 节点 加入栈 current = current.left; } else { // 3. 如果碰到了叶子节点 就取出栈的元素 判断值是否小于上一个节点的值 current = stack.pop(); // 4. 如果小于 证明不是二叉搜索树 因为二叉搜索树 左 - 中 - 右 应该是递增的顺序 if (pre !== null && current.val < pre.val) { return false; } // 5. 修改上一个节点的值 为当前的节点 pre = current; // 6. 中序遍历 修改游标 current = current.right; } } return true } module.exports = { isValidBST: isValidBST, };
function isValidBST( root ) { // write code here //中序遍历 let a=[] function mid(root){ if(!root) return mid(root.left) a.push(root.val) mid(root.right) } //写完了别忘记调用呀 mid(root) for(let i=0;i<=a.length-2;i++){ if(a[i]>a[i+1]) return false } return true }