每日一题：剑指 Offer 33. 二叉搜索树的后序遍历序列

妖狐艹你老母 2023-10-11 17:28 23阅读 0赞

今天带大家通过一道相对比较难的题再来看看分治和递归的思想

题目描述:

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

题目示例：  
![在这里插入图片描述][f71ac1a8bfa84c40a487557457b3f7fd.png_pic_center]

首先这道题，我们先关注两点：

*  1.二叉搜索树
 *  2.后序遍历

什么叫二叉搜索树，即存在左子树的话，则左子树的值都小于根节点，存在右子树的话，则右子树的每一个结点都大于根节点。

后序遍历有什么特点呢？

首先后序遍历的顺序是：左子树->右子树->根节点

两个结合起来，那么首先可以确定的就是：如果给出后序遍历序列，那么最后一个结点一定是根节点，我们还是以题目示例为例：  
nums=\[1,3,2,6,5\]  
递归，就要有递归的方向和步骤，即重复哪些步骤，

首先我们可以确定根节点5，其次我们也可确定第一个右子树的结点:从下标0开始去找，找出第一个大于根节点的值，记录其下标为m，则m的左侧就是左子树，右侧就是右子树，然后重复该过程，即确定根节点，找到第一个大于根节点的值，划分左右子树。

6是第一个大于根节点5的元素，其下标为：3，则\[0,m-1\]即\[0,2\]为左子树，\[m,length-2\]，因为length-1对应的是根节点的位置，即：\[3,3\]为右子树，此时我们还需要判读什么时候是递归结束的位置，首先我们定义起始点为：i，最右侧结点位置为：j，则i>=j时说明树中的结点已经全部查找结束。

我们现在一直说的是符合的情况，那么不符合 二叉搜索树后续遍历的特点是什么情况呢？

首先我们要知道，在上面我们确定第一个大于根节点的步骤中，其实已经确定好左子树全部都符合，所以我们只需要判断右子树里的所有结点是否全部都大于根节点，如果不大于那么就说明这个序列不是一个后序遍历的序列。

根据以上思路，我们把代码写一下：

public boolean verifyPostorder(int[] postorder) {
        
            return dfs(postorder, 0, postorder.length - 1);
        }
    
        boolean flag = true;
    
        public boolean dfs(int[] postorder, int i, int j) {
        
            if (i >= j) return true;//递归结束条件
            //找到第一个大于根节点的下标
            int p = i;
            while (postorder[p] < postorder[j]) p++;
            int m = p;//使用m来保存第一个大于根节点的下标
            //再接着判断右子树的所有结点是否都大于根节点
            while (p < j) {
        
                if (postorder[p] < postorder[j]) return false;
                p++;
            }
            flag = dfs(postorder, i, m - 1);//看看左子树是否符合条件
            if (!flag) return false;
            flag = dfs(postorder, m, j - 1);//看看右子树是否符合
            if (!flag) return false;
            return flag;
        }

![在这里插入图片描述][6fb730061aea4a7db8f751e8c67d1a33.png_pic_center]

[f71ac1a8bfa84c40a487557457b3f7fd.png_pic_center]: https://img-blog.csdnimg.cn/f71ac1a8bfa84c40a487557457b3f7fd.png#pic_center
[6fb730061aea4a7db8f751e8c67d1a33.png_pic_center]: https://img-blog.csdnimg.cn/6fb730061aea4a7db8f751e8c67d1a33.png#pic_center