LeetCode题解:98. 验证二叉搜索树,递归中序遍历过程中判断,JavaScript,详细注释
程序员文章站
2022-03-27 12:38:10
解题思路:参考官方题解中的中序遍历动画,可知中序遍历的顺序为从左到右。也就是说,可以使用递归中序遍历,在输出结果过程中,判断相邻两个节点是否递增即可。中序遍历的方法可以参考我的题解LeetCode题解:94. 二叉树的中序遍历,递归,JavaScript,详细注释/** * @param {TreeNode} root * @return {boolean} */var isValidBST = function (root) { let prev = -Infinity; // 保...
原题链接:https://leetcode-cn.com/problems/validate-binary-search-tree/
解题思路:
- 参考官方题解中的中序遍历动画,可知中序遍历的顺序为从左到右。
- 也就是说,可以使用递归中序遍历,在输出结果过程中,判断相邻两个节点是否递增即可。
- 中序遍历的方法可以参考我的题解LeetCode题解:94. 二叉树的中序遍历,递归,JavaScript,详细注释
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function (root) {
let prev = -Infinity; // 保存上一个节点的值
// 中序遍历二叉树
function traversal(node) {
if (node) {
// 缓存遍历左子节点的结果
const leftResult = traversal(node.left);
// 如果当前节点的值比上一个节点的值小,即为非二叉搜索树
if (prev >= node.val) {
return false;
}
// 当前节点即为下一次递归上一个节点
prev = node.val;
// 缓存遍历右子节点的结果
const rightResult = traversal(node.right);
// 左右子树必须都满足条件,采薇二叉搜索树
return leftResult && rightResult;
}
// 如果当前节点为空,则默认返回true
return true;
}
return traversal(root);
};
本文地址:https://blog.csdn.net/chencl1986/article/details/109244140
上一篇: SSM整合版本一之普通的CRUD
下一篇: 小话设计模式之 迭代器(PHP)