剑指Offer-面试题33-二叉搜索树的后序遍历序列

2020-05-03

题目描述

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

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

示例1:

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

示例2：

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

提示：数组长度 <= 1000

思路

通过递归判断所有子树的正确性（后序遍历是否满足二叉搜索树的定义）
递归解析：
- 终止条件：当i>=j，说明此子树节点数量<=1，直接返回true
- 递归流程：
  1. 划分左右子树：遍历后序遍历的[i,j]区间元素，寻找第一个大于根节点的节点，索引记为m。左子树区间为[i,m-1]，右子树区间为[m,j-1]，根节点索引为j。
  2. 判断是否为二叉搜索树：左子树区间[i,m-1]内元素都要<postorder[j]。在1.划分左右子树区间时已经保证左子树区间的正确性，因此只需判断右子树区间即可。右子树区间[m,j-1]内元素都要>postorder[j]。当遇到<=postorder[j]的元素则跳出，通过p==j判断是否为二叉搜索树。
  3. 返回值：
    1. p==j：判断此树是否正确
    2. recur(i,m-1)：判断此树的左子树是否正确
    3. recur(m,j-1)：判断此树的右子树是否正确

代码

class Solution{
    public boolean verifyPostorder(int[] postorder){
        return recur(postorder,0,postorder.length-1);
    }
    //递归判断树的正确性
    public boolean recur(int[] postorder,int i,int j){
        if(i >= j){ //若i>=j，说明树的节点<=1，返回true
            return true;
        }
        int p = i;  //遍历寻找第一个大于根节点的节点
        while(postorder[p] < postorder[j]){
            p++;
        }
        int m = p;  //找到，索引记为m
        //从这个大于根节点的节点开始向后遍历，验证右子树区间的正确性
        while(postorder[p] > postorder[j]){ 
            p++;
        }
        //若p=j，说明当前树右子树区间正确，递归判断左子树区间和右子树区间
        return p==j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。