江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第255题：验证前序遍历序列二叉搜索树

给定一个整数数组，你需要验证它是否是一个二叉搜索树的前序遍历序列。 二叉搜索树的定义如下： - 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； - 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； - 任意节点的左、右子树也分别为二叉搜索树。

题目描述

给定一个整数数组，你需要验证它是否是一个二叉搜索树的前序遍历序列。

二叉搜索树的定义如下：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉搜索树。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入: [5,2,1,3,6]
输出: true

示例 2：

输入: [5,2,6,1,3]
输出: false

提示

  • 1 <= preorder.length <= 10^4
  • 1 <= preorder[i] <= 10^4
  • preorder 中的所有值互不相同

解题思路

方法一：递归方法

我们可以根据二叉搜索树的性质和前序遍历的特点来解决这个问题。前序遍历的顺序是：根节点，左子树，右子树。对于二叉搜索树来说，左子树的所有节点值都小于根节点值，右子树的所有节点值都大于根节点值。

关键点

  • 前序遍历序列的第一个元素是根节点
  • 根据二叉搜索树的特性，可以找到左右子树的分界点
  • 递归验证左子树和右子树是否也满足二叉搜索树的前序遍历特性
  • 需要确保左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值

具体步骤

  1. 设置有效的取值范围 [lower, upper]
  2. 使用一个索引 index 遍历前序遍历序列
  3. 对于当前节点，检查其值是否在有效范围内
  4. 如果当前节点的值小于 upper 但大于 lower，则继续处理左子树和右子树
  5. 否则，返回 false

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度。最坏情况下，我们需要访问数组中的每个元素一次。
  • 空间复杂度：O(n)，递归调用的栈空间，最坏情况下可能达到 O(n)。

方法二：单调栈

另一种更高效的方法是使用单调栈。在前序遍历中，我们总是先访问一个节点，然后是它的左子树，再是它的右子树。当我们遍历到一个节点时，如果它小于栈顶，说明它是左子节点；如果它大于栈顶，说明我们已经处理完一个子树，现在在处理栈中某个节点的右子树。

关键点

  • 使用一个单调递减栈来模拟前序遍历的过程
  • 栈中保存的是已经访问过的节点，这些节点可能是当前节点的祖先
  • 当遇到一个大于栈顶的值时，说明我们开始访问某个节点的右子树
  • 使用一个变量 lower 记录当前允许的最小值

具体步骤

  1. 初始化一个空栈和一个 lower 变量为负无穷
  2. 遍历前序遍历序列中的每个节点：
    • 如果当前节点的值小于 lower，返回 false
    • 当栈不为空且当前节点的值大于栈顶元素时，表示我们开始访问右子树：
      • 不断弹出栈顶元素，并更新 lower 为最后一个弹出的元素
    • 将当前节点入栈
  3. 如果遍历完成没有返回 false，则返回 true

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多入栈和出栈各一次。
  • 空间复杂度：O(n)，最坏情况下栈可能包含所有元素。

方法三：空间优化的单调栈

我们可以进一步优化方法二，重用输入数组作为栈，从而将空间复杂度降低到 O(1)。

图解思路

方法一：递归验证过程分析表

以示例 1：[5,2,1,3,6] 为例

子数组 根节点 有效范围 左子树 右子树 结果
[5,2,1,3,6] 5 [-∞, +∞] [2,1,3] [6] 递归判断
[2,1,3] 2 [-∞, 5] [1] [3] 递归判断
[1] 1 [-∞, 2] [] [] true
[3] 3 [2, 5] [] [] true
[6] 6 [5, +∞] [] [] true
最终结果 - - - - true

方法二：单调栈分析表

以示例 1：[5,2,1,3,6] 为例

遍历到的节点 当前栈 lower 操作 结果
初始状态 [] -∞ - -
5 [5] -∞ 入栈 继续
2 [5,2] -∞ 入栈 继续
1 [5,2,1] -∞ 入栈 继续
3 [5,3] 2 1<3，弹出1，更新lower=2；3>2，入栈 继续
6 [6] 5 3<6，弹出3和5，更新lower=5；6>5，入栈 继续
遍历结束 [6] 5 验证完成 true

代码实现

C# 实现

public class Solution {
    // 方法一：递归
    private int index = 0;
    
    public bool VerifyPreorder1(int[] preorder) {
        if (preorder == null || preorder.Length == 0) {
            return true;
        }
        return Verify(preorder, int.MinValue, int.MaxValue);
    }
    
    private bool Verify(int[] preorder, int lower, int upper) {
        if (index >= preorder.Length) {
            return true;
        }
        
        int val = preorder[index];
        if (val <= lower || val >= upper) {
            return false;
        }
        
        index++;
        // 验证左子树
        bool left = Verify(preorder, lower, val);
        // 验证右子树
        bool right = Verify(preorder, val, upper);
        
        return left && right;
    }
    
    // 方法二：单调栈
    public bool VerifyPreorder(int[] preorder) {
        if (preorder == null || preorder.Length == 0) {
            return true;
        }
        
        Stack<int> stack = new Stack<int>();
        int lower = int.MinValue;
        
        foreach (int val in preorder) {
            // 如果当前值小于最小下界，不满足BST的性质
            if (val < lower) {
                return false;
            }
            
            // 当遇到一个大于栈顶的值，说明开始处理右子树
            while (stack.Count > 0 && val > stack.Peek()) {
                lower = stack.Pop(); // 更新下界
            }
            
            // 将当前值入栈
            stack.Push(val);
        }
        
        return true;
    }
    
    // 方法三：空间优化的单调栈
    public bool VerifyPreorder3(int[] preorder) {
        if (preorder == null || preorder.Length == 0) {
            return true;
        }
        
        int stackIdx = -1; // 栈顶指针
        int lower = int.MinValue;
        
        foreach (int val in preorder) {
            // 如果当前值小于最小下界，不满足BST的性质
            if (val < lower) {
                return false;
            }
            
            // 当遇到一个大于栈顶的值，说明开始处理右子树
            while (stackIdx >= 0 && val > preorder[stackIdx]) {
                lower = preorder[stackIdx--]; // 更新下界
            }
            
            // 将当前值入栈
            preorder[++stackIdx] = val;
        }
        
        return true;
    }
}

Python 实现

class Solution:
    # 方法一：递归
    def verifyPreorder1(self, preorder: List[int]) -> bool:
        if not preorder:
            return True
        
        self.index = 0
        
        def verify(lower, upper):
            if self.index >= len(preorder):
                return True
            
            val = preorder[self.index]
            if val <= lower or val >= upper:
                return False
            
            self.index += 1
            # 验证左子树
            if not verify(lower, val):
                return False
            # 验证右子树
            return verify(val, upper)
        
        return verify(float('-inf'), float('inf'))
    
    # 方法二：单调栈
    def verifyPreorder(self, preorder: List[int]) -> bool:
        if not preorder:
            return True
        
        stack = []
        lower = float('-inf')
        
        for val in preorder:
            # 如果当前值小于最小下界，不满足BST的性质
            if val < lower:
                return False
            
            # 当遇到一个大于栈顶的值，说明开始处理右子树
            while stack and val > stack[-1]:
                lower = stack.pop()  # 更新下界
            
            # 将当前值入栈
            stack.append(val)
        
        return True
    
    # 方法三：空间优化的单调栈
    def verifyPreorder3(self, preorder: List[int]) -> bool:
        if not preorder:
            return True
        
        stack_idx = -1  # 栈顶指针
        lower = float('-inf')
        
        for i, val in enumerate(preorder):
            # 如果当前值小于最小下界，不满足BST的性质
            if val < lower:
                return False
            
            # 当遇到一个大于栈顶的值，说明开始处理右子树
            while stack_idx >= 0 and val > preorder[stack_idx]:
                lower = preorder[stack_idx]  # 更新下界
                stack_idx -= 1
            
            # 将当前值入栈
            stack_idx += 1
            preorder[stack_idx] = val
        
        return True

C++ 实现

class Solution {
public:
    // 方法一：递归
    bool verifyPreorder1(vector<int>& preorder) {
        if (preorder.empty()) {
            return true;
        }
        
        index = 0;
        return verify(preorder, INT_MIN, INT_MAX);
    }
    
    // 方法二：单调栈
    bool verifyPreorder(vector<int>& preorder) {
        if (preorder.empty()) {
            return true;
        }
        
        stack<int> stk;
        int lower = INT_MIN;
        
        for (int val : preorder) {
            // 如果当前值小于最小下界，不满足BST的性质
            if (val < lower) {
                return false;
            }
            
            // 当遇到一个大于栈顶的值，说明开始处理右子树
            while (!stk.empty() && val > stk.top()) {
                lower = stk.top();  // 更新下界
                stk.pop();
            }
            
            // 将当前值入栈
            stk.push(val);
        }
        
        return true;
    }
    
    // 方法三：空间优化的单调栈
    bool verifyPreorder3(vector<int>& preorder) {
        if (preorder.empty()) {
            return true;
        }
        
        int stackIdx = -1;  // 栈顶指针
        int lower = INT_MIN;
        
        for (int val : preorder) {
            // 如果当前值小于最小下界，不满足BST的性质
            if (val < lower) {
                return false;
            }
            
            // 当遇到一个大于栈顶的值，说明开始处理右子树
            while (stackIdx >= 0 && val > preorder[stackIdx]) {
                lower = preorder[stackIdx--];  // 更新下界
            }
            
            // 将当前值入栈
            preorder[++stackIdx] = val;
        }
        
        return true;
    }

private:
    int index;
    
    bool verify(vector<int>& preorder, int lower, int upper) {
        if (index >= preorder.size()) {
            return true;
        }
        
        int val = preorder[index];
        if (val <= lower || val >= upper) {
            return false;
        }
        
        index++;
        // 验证左子树
        bool left = verify(preorder, lower, val);
        // 验证右子树
        bool right = verify(preorder, val, upper);
        
        return left && right;
    }
};

执行结果

C# 实现

  • 执行用时：88 ms
  • 内存消耗：40.2 MB

Python 实现

  • 执行用时：48 ms
  • 内存消耗：16.8 MB

C++ 实现

  • 执行用时：16 ms
  • 内存消耗：13.7 MB

性能对比

语言 执行用时 内存消耗 特点
C# 88 ms 40.2 MB 性能中等，代码结构清晰
Python 48 ms 16.8 MB 代码简洁，性能良好
C++ 16 ms 13.7 MB 性能最佳，内存占用最小

代码亮点

  1. 🎯 提供了三种不同的解法，从递归到单调栈再到空间优化，思路清晰
  2. 💡 单调栈解法巧妙地利用了前序遍历和BST的性质，通过更新下界来验证右子树
  3. 🔍 空间优化版本重用输入数组作为栈，实现了O(1)的额外空间复杂度
  4. 🎨 代码组织结构良好，变量命名有意义，各方法独立且逻辑清晰

常见错误分析

  1. 🚫 没有正确处理空数组的边界情况
  2. 🚫 在递归方法中没有正确维护索引，导致重复处理节点
  3. 🚫 在单调栈方法中错误地更新下界，导致验证结果不正确
  4. 🚫 在O(1)空间复杂度解法中错误地修改了原输入数组，可能影响后续使用

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
递归 O(n) O(n) 思路直观，容易理解 需要全局索引，递归开销大
单调栈 O(n) O(n) 迭代实现，避免递归开销 需要额外O(n)空间
优化单调栈 O(n) O(1) 空间复杂度最优 修改了输入数组，可能不适用于所有场景

相关题目