本文共 972 字，大约阅读时间需要 3 分钟。

验证后序遍历序列是否为二叉搜索树

二叉搜索树的后序遍历序列验证方法

在二叉搜索树的后序遍历中，根节点总是最后一个访问的节点。通过这一特性，我们可以高效地验证给定的后序遍历序列是否构成二叉搜索树。

验证步骤如下

如何判断序列不是二叉搜索树

如果在验证过程中发现某个节点的右子节点的值小于或等于根节点的值，或者左子节点的值大于或等于根节点的值，那么这个序列就不是二叉搜索树。

代码实现

class Solution {public:    bool verifyPostorder(vector
   
    & postorder) {        return dfs(postorder, 0, postorder.size() - 1);    }    bool dfs(vector
    
     & postorder, int left, int right) {        if (left >= right) return true;        int val = postorder[right];        int k = left;        while (k < right && postorder[k] <= val) {            k++;        }        if (k == left) return false;        int root = right;        right = k - 1;        if (root == -1) return true;        return dfs(postorder, left, root) && dfs(postorder, root + 1, right);    }}
    
   

该代码使用递归的方式验证后序遍历序列是否为二叉搜索树。首先找到根节点，然后确定左子节点和右子节点的范围，最后递归验证左右子树是否满足二叉搜索树的性质。

通过这种方法可以有效地判断给定的后序遍历序列是否构成二叉搜索树。

转载地址：http://sjqv.baihongyu.com/