难度: Medium
Submission
运行时间: 36 ms
内存: 17.6 MB
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = []
lo = float('-inf')
for num in preorder:
if num < lo:
return False
while stack and num > stack[-1]:
lo = stack.pop()
stack.append(num)
return True
Explain
这个题解是利用单调栈来验证前序遍历序列是否满足二叉搜索树的性质。遍历前序序列，对于每个当前节点，其值必须大于之前遍历过的所有节点（即栈中的所有元素）。如果当前节点小于栈顶元素，说明不满足二叉搜索树，返回 false。否则，将栈中小于当前节点的元素全部弹出，更新下界 lo，并将当前节点入栈。最后遍历完整个序列没有返回 false，说明满足二叉搜索树，返回 true。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = []
lo = float('-inf') # 初始化下界为负无穷
for num in preorder:
if num < lo: # 如果当前节点小于下界，不满足二叉搜索树性质
return False
while stack and num > stack[-1]: # 将栈中小于当前节点的元素全部弹出
lo = stack.pop() # 更新下界
stack.append(num) # 将当前节点入栈
return True # 遍历完整个序列，满足二叉搜索树性质
Explore
在题解中，`lo`代表了二叉搜索树中当前节点的最小允许值。因为二叉搜索树的定义要求左子树中的所有节点必须小于其根节点，而右子树的所有节点必须大于其根节点。在算法开始时，下界`lo`被初始化为负无穷，这意味着序列的第一个节点可以是任何整数值，因为还没有任何限制条件被设置。随着算法的进行，每次从栈中弹出元素时，都会更新这个下界，确保新的节点值必须大于这个下界，从而保证了这个序列能够正确地代表一个二叉搜索树的前序遍历。设置为负无穷是为了使第一个节点不受限制，且能适应任何整数范围的输入。
在前序遍历中，栈被用来记录路径，其中栈顶元素代表当前路径上最后一个没有完全处理其右子树的节点。当遇到一个新节点小于栈顶元素时，这意味着新节点属于当前栈顶节点的左子树。但是，如果新节点大于栈顶元素，则表示我们已经开始遍历新的栈顶元素的右子树。因此，需要持续弹栈直到找到这个新节点的正确位置，即找到一个节点，使得新节点小于这个节点但大于前一个弹出的节点（或下界`lo`）。这个操作确保了新节点插入到正确的位置，维护了二叉搜索树的性质，并正确地更新了下界值，从而为后续节点的验证提供了正确的比较基准。
在二叉搜索树中，任何节点的右子节点以及其子树中的所有节点都必须大于该节点。当栈中的元素被弹出时，表示我们正在处理某个节点的右子树。下界`lo`被设置为该节点的值，确保所有后续节点（即这个被弹出节点的右子树中的节点）必须大于这个值。如果后续遇到的当前节点小于这个下界`lo`，则意味着存在一个节点位于其上一个节点（或更早的祖先节点）的右子树中，但其值小于该祖先节点，这违反了二叉搜索树的基本性质，因此算法返回`false`。这种检查机制保证了整个序列可以形成一个有效的二叉搜索树的结构。