剑指 Offer 33. 二叉搜索树的后序遍历序列

小鱼儿 2022-12-16 06:40 101阅读 0赞

# 题目 #

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

参考以下这颗二叉搜索树：  
![在这里插入图片描述][20201019141854438.png_pic_center]

示例 1：

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

示例 2：

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

提示：  
数组长度 <= 1000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof][https_leetcode-cn.com_problems_er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof]

# 解题思路 #

首先看清题目

*  二叉搜索树-左节点的值小于根节点,右节点的值大于根节点
 *  后序遍历-左右根

使用递归的思想,判断当前树,左子树和右子树

*  区间范围为\[start,end\],递归终止条件start>=end
 *  使用temp作为临时下标,初始化为start,向右移动,直到遇到第一个不小于end下标值的下标,下标记为pos
 *  temp继续后移,直到遇到第一个不大于end下标值的下标
 *  判断当前树是否正确,即temp == end
 *  左子树的范围为\[start, pos - 1\],递归判断左子树
 *  右子树的范围为\[pos, end - 1\],递归判断右子树

# 代码 #

class Solution { 
        public boolean verifyPostorder(int[] postorder) { 
            // 校验
            if (postorder == null) { 
                return false;
            }
    
            return backTrack(postorder, 0, postorder.length - 1);
        }
    
        private boolean backTrack(int[] postorder, int start, int end) { 
            // 递归终止条件
            if (start >= end) { 
                return true;
            }
    
            // 初始化temp下标
            int temp = start;
            // 当temp下标的值小于end下标的值时,不断后移,直到找到第一个不小于end下标值的下标
            while (postorder[temp] < postorder[end]) { 
                temp++;
            }
    
            // 记录第一个大于end下标值的下标,用于区分左子树和右子树
            int pos = temp;
            // 当temp下标的值大于end下标的值时,不断后移,直到找到第一个不大于end下标值的下标
            while (postorder[temp] > postorder[end]) { 
                temp++;
            }
    
            // 判断当前树是否正确
            // 判断左子树-递归判断(start, pos - 1)
            // 判断右子树-递归判断(pos, end - 1)
            return temp == end && backTrack(postorder, start, pos - 1) && backTrack(postorder, pos, end - 1);
        }
    }

[20201019141854438.png_pic_center]: /images/20221123/18065907df334ea1959690a422f1d83f.png
[https_leetcode-cn.com_problems_er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof