- 难度:
中等
- 本题涉及算法:
中序遍历
- 思路:
中序遍历
- 类似题型:
题目 98. 验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
方法一
解题思路
- 中序遍历时,判断当前节点是否大于中序遍历的前一个节点,如果大于,说明满足 BST,继续遍历;否则直接返回 false。
java
class Solution { long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } // 访问左子树 if (!isValidBST(root.left)) { return false; } // 访问当前节点:如果当前节点小于等于中序遍历的前一个节点,说明不满足BST,返回 false;否则继续遍历。 if (root.val <= pre) { return false; } pre = root.val; // 访问右子树 return isValidBST(root.right); } }
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 中序遍历 : 按照 左 中 右 的顺序 挨个遍历
class Solution:
cur = float("-inf")
def isValidBST(self, root: TreeNode) -> bool:
if root is None:
return True
# 访问左子树
if not self.isValidBST(root.left):
return False
# 访问当前节点:如果当前节点小于等于中序遍历的前一个节点,说明不满足BST,返回 false;否则继续遍历。
if (root.val <= self.cur):
return False
self.cur = root.val
# 访问右子树
return self.isValidBST(root.right)
PREVIOUS102. 二叉树的层序遍历
NEXT81. 搜索旋转排序数组 II