# ACM 选手图解 LeetCode 验证二叉搜索树

LeetCode 98：验证二叉搜索树

• 树中节点数目范围在 [1,10^4] 内。
• -2^31 <= Node.val <= 2^31 - 1。

(1) 找出重复的子问题。

inOrder(root.left)
print(root.val)
inOrder(root.right)

(2) 确定终止条件。

if root == None:
return 

Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
# 中序遍历
def inOrder(self, root: TreeNode, res):
if root == None:
return
self.inOrder(root.left, res)
res.append(root.val)
self.inOrder(root.right, res)
def isValidBST(self, root: TreeNode) -> bool:
res = []
self.inOrder(root, res)
# 判断 res 是否有序
for i in range(1, len(res)):
if num[i] <= nums[i - 1]:
return False
return True

Java 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
// 中序遍历
public void inOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inOrder(root.left, res);
inOrder(root.right, res);
}
public boolean isValidBST(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inOrder(root, res);
// 判断 res 是否有序
for(int i = 1; i < res.size(); i++){
if(res.get(i) <= res.get(i - 1)){
return false;
}
}
return true;
}
}

• 初始化一个空栈。
• 当【根节点不为空】或者【栈不为空】时，从根节点开始
• 若当前节点有左子树，一直遍历左子树，每次将当前节点压入栈中。
• 若当前节点无左子树，从栈中弹出该节点，尝试访问该节点的右子树。

stack = []
# 记录前一个节点
pre = None

# 一直向左子树走，每一次将当前节点保存到栈中
if root:
stack.append(root)
root = root.left

cur = stack.pop()
# 判断序列是否有序
if pre and cur.val <= pre.val:
return False
pre = cur
root = cur.right

Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack = []
# 记录前一个节点
pre = None
while root or stack:
# 一直向左子树走，每一次将当前节点保存到栈中
if root:
stack.append(root)
root = root.left
# 当前节点为空，证明走到了最左边，从栈中弹出节点
# 开始对右子树重复上述过程
else:
cur = stack.pop()
# 判断序列是否有序
if pre and cur.val <= pre.val:
return False
pre = cur
root = cur.right
return True

Java 代码实现

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
// 记录前一个节点
TreeNode pre = null;
while(stack.size() > 0 || root != null){
// 一直向左子树走，每一次将当前节点保存到栈中
if(root != null){
root = root.left;
}
// 当前节点为空，证明走到了最左边，从栈中弹出节点
// 开始对右子树重复上述过程
else{
TreeNode cur = stack.pop();
// 判断序列是否有序
if(pre != null && cur.val <= pre.val){
return false;
}
pre = cur;
root = cur.right;
}
}
return true;
}
}

|
3月前
|

[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
[Java·算法·简单] LeetCode 125. 验证回文串 详细解读
42 0
|
2月前
|

LeetCode 题目 95：从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95：从递归到动态规划实现 不同的二叉搜索树 II
17 0
|
1天前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案，通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
11 6
|
2月前
|

LeetCode 题目 96：从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96：从动态规划、递归到卡塔兰数实现不同的二叉搜索树
23 2
|
2月前

18 0
|
3月前
|

【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
【LeetCode】剑指 Offer 54. 二叉搜索树的第k大节点
30 1
|
2月前
|

17 0
|
2月前
|
canal 算法 数据可视化
LeetCode 125题：验证回文串
LeetCode 125题：验证回文串
19 0
|
2月前
|

【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 125. 验证回文串(Java/C/Python3实现含注释说明,Easy)
13 0
|
3月前
leetcode代码记录（不同的二叉搜索树
leetcode代码记录（不同的二叉搜索树
19 0