LeetCode 98. 验证二叉搜索树

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 98. 验证二叉搜索树

思路分析

中序遍历为升序

使用一个栈来模拟中序遍历。

初始化一个变量 pre，用于记录前一个节点的值。

遍历二叉树，将左子树的节点依次压入栈中。

弹出栈顶节点，比较当前节点的值和 pre 的值。

如果当前节点的值小于等于 pre 的值，则返回 false。

否则，更新 pre 的值为当前节点的值，并继续遍历右子树。

参考代码

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	var stack []*TreeNode
	pre := math.MinInt64

	for len(stack) > 0 || root != nil {
		// 将左子树的节点依次压入栈中
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		// 弹出栈顶节点
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		// 比较当前节点的值和 pre 的值
		if root.Val <= pre {
			return false
		}
		pre = root.Val

		// 遍历右子树
		root = root.Right
	}

	return true
}

时间复杂度：O (N)，其中 N 是二叉树的节点数。我们需要遍历每个节点一次。

空间复杂度：O (N)，在最坏情况下，栈的深度可能达到 N。

func isValidBST(root *TreeNode) bool {
	return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, low, high int) bool {
	if node == nil {
		return true
	}
	if node.Val <= low || node.Val >= high {
		return false
	}
	return validate(node.Left, low, node.Val) && validate(node.Right, node.Val, high)
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/83568790