验证二叉搜索树的前序遍历序列
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 17.6 MB
/*
* Leetcode题目: 验证二叉搜索树的前序遍历序列
* 思路:
* 1. 利用栈来辅助判断是否为前序遍历序列
* 2. 使用一个变量low来跟踪当前子树的最小值
* 3. 使用Java Stream API来简化遍历逻辑
*/
import java.util.Stack;
import java.util.Arrays;
public class ValidatePreorderBSTStream {
public boolean verifyPreorder(int[] preorder) {
Stack<Integer> stack = new Stack<>();
int[] low = {Integer.MIN_VALUE};
return Arrays.stream(preorder).allMatch(value -> {
if (value < low[0]) {
return false;
}
while (!stack.isEmpty() && value > stack.peek()) {
low[0] = stack.pop();
}
stack.push(value);
return true;
});
}
}解释
方法:
这个题解是利用单调栈来验证前序遍历序列是否满足二叉搜索树的性质。遍历前序序列，对于每个当前节点，其值必须大于之前遍历过的所有节点（即栈中的所有元素）。如果当前节点小于栈顶元素，说明不满足二叉搜索树，返回 false。否则，将栈中小于当前节点的元素全部弹出，更新下界 lo，并将当前节点入栈。最后遍历完整个序列没有返回 false，说明满足二叉搜索树，返回 true。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中，下界`lo`的初始值为什么设为负无穷，这对算法的正确性有什么影响？
▷🦆
为什么在遍历时，遇到当前节点小于栈顶元素时要持续弹栈，这个操作的目的是什么？
▷🦆
题解中提到，如果当前节点小于下界`lo`则返回`false`，这种情况具体是如何违反二叉搜索树的性质的？
▷
