写点什么

LeetCode 题解:98. 验证二叉搜索树,使用栈中序遍历,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 10 月 20 日
LeetCode题解:98. 验证二叉搜索树,使用栈中序遍历,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/validate-binary-search-tree/


解题思路:


  1. 参考官方题解中的中序遍历动画,可知中序遍历的顺序为从左到右。

  2. 也就是说,只要在进行中序遍历的同时,判断节点的值是否从左到右递增即可。

  3. 中序遍历的方法可以参考我的题解LeetCode题解:94. 二叉树的中序遍历,使用栈,JavaScript,详细注释


/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function (root) {
let stack = []; // 使用栈进行遍历
let current = root; // 使用节点进行遍历
let prev = -Infinity; // 记录前一个节点的值,初始为负无穷大
// 中序遍历二叉树
// 遍历的过程中,可能出现current为空,而stack中有元素,即为遍历到树的最底端。
// 也可能出现current有值而stack为空的情况,如遍历到二叉树的根节点。
while (current || stack.length) {
// 不断向左下遍历节点,同时将所有节点入栈
// 这样就保证了总是从最左端开始遍历节点
while (current) {
stack.push(current);
current = current.left;
}
// 从栈中弹出节点,即为当前遍历的节点
// 弹出节点的顺序为从左到右。
current = stack.pop();
// 将当前节点的值,与前一个节点比较
// 如果当前值小于前一个节点,则二叉搜索树不合法,直接退出循环
if (prev >= current.val) {
return false;
}
// 将当前节点的值存储为前一个节点,供下一次遍历判断
prev = current.val;
// 不断向右侧遍历树,如果右侧节点为空,则会从栈中弹出当前子树的根节点
// 这样就形成了从左到右的遍历顺序
current = current.right;
}
return true;
};
复制代码


发布于: 2020 年 10 月 20 日阅读数: 33
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:98. 验证二叉搜索树,使用栈中序遍历,JavaScript,详细注释