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

题目：二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

     5

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

示例 2：

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

提示：数组长度 <= 1000

解题：

方法一：递归

已知条件： 后序序列最后一个值为root；二叉搜索树左子树的值都比root小，右子树的值都比root大。

步骤：

1. 确定根节点root；
2. 遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；
3. 遍历右子树，若发现有小于root的值，则直接返回false；
4. 分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。

class Solution {public:    bool verifyPostorder(vector
   
    & postorder) {        bool res = true;        if (postorder.empty())            return res;        res = helper(postorder,0,postorder.size()-1);        return res;    }    bool helper(vector
    
     & postorder, int start, int end)    {        if (postorder.empty() || start > end)            return true;        //根结点        int root = postorder[end];        //在二叉搜索树中左子树的结点小于根结点        int i = start;        for(;i
     
       root)                break;        }        //在二叉搜索书中右子树的结点大于根结点        for(int j = i;j
      
       start)        {            left = helper(postorder,start,i-1);        }        //判断右子树是不是二叉搜索树        bool right = true;        if (i
      
     
    
   

方法二：

class Solution {    bool helper(vector
   
    & post,int lo, int hi){        if(lo >= hi) return true; //单节点或空节点返回true        int root = post[hi]; //后序遍历序列最后的值为根节点的值        int l = lo;        while(l
    
     root)            r++; //遍历右子树(值大于根)，右子树序列post[l, r);        if(r != hi) return false;//若未将post[l, hi)遍历完，则非后序遍历序列 返回false        return helper(post, lo, l-1) && helper(post, l, hi-1); //递归检查左右子树    }public:    bool verifyPostorder(vector
     
      & postorder) {        return helper(postorder,0,postorder.size()-1);    }};
     
    
   

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