【剑指offer】面试题33：二叉搜索树的后序遍历序列

素颜马尾好姑娘i 2022-03-29 11:53 152阅读 0赞

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

牛客网链接： [https://blog.csdn.net/jsqfengbao/article/details/47281789][https_blog.csdn.net_jsqfengbao_article_details_47281789]

下面先看个案例了解下这个题目的意思。

![2019010815504820.png][]

如上图的二叉搜素树所示，如果输入的数组为\{5，7，6，9，11，10，8\}，则返回true。

**重要的是-->了解二叉搜索树后序遍历的特点：**

**在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树结点的值，它们都比根节点的值大。**

以数组｛5，7，6，9，11，10，8｝为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5，7和6都比8小，是值为8的节点的左子树节点；后3个数字9，11和10都比 8 大，是值为8的结点的右子树结点。

我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个**递归**的过程。对于序列5，7，6，最后一个数字6是左子树的根节点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子节点。同样，在序列9，11，10中，最后一个数字10是右子树的根节点，数字9比10小，是值为10的结点的左子结点，而11则是它的右子节点。

我们再来分析一下另一个数组｛7，4，6，5｝。后序遍历的最后一个树是根节点，因此根节点的值是5。由于第一个数字7比5大，因此对应的二叉搜索树中，根节点上是没有左子树的，数字7，4，和6都是右子树结点的值。但我们发现在右子树中有一个结点的值是4，比根节点的值5小，这违背了二叉搜索树的定义。因此不存在一颗二叉搜索树，它的后序遍历的结果是｛7，4，6，5｝。

具体实现代码如下：

/**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
     * 如果是则返回 true，否则返回 false。
     * 假设输入的数组的任意两个数字都互不相同。
     */
    public class LastSequenceOfTree {
    
    	public boolean verifySquenceOfBST(int[] sequence,int start, int end){
    		if(sequence == null || sequence.length <= 0){
    			return true;
    		}
    		
    		if(start < 0 || end > sequence.length){
    			throw new IllegalArgumentException("The arguments is error");
    		}
    
    		// 根节点就是序列中的最后一个值
    		int root = sequence[end];
    		
    		// 在二叉搜索树中左子树的结点小于根节点
    		int i = 0;
    		for(; i < end; i++){
    			if(sequence[i] > root){
    				// 比root小的都是root的左子节点
    				break;
    			}
    		}
    		
    		// 在二叉搜索树中右子树的结点大于根节点
    		int j = i;
    		for(; j < end; j++){
    			if(sequence[j] < root){
    				// sequence[j]到sequence[end - 1]都是root的右子树节点
    				// 必须比根节点大，如果出现小的情况，则直接返回false
    				return false;
    			}
    		}
    		
    		// 判断左子树是不是二叉搜索树
    		boolean left = true;
    		if(i > 0){
    			left = verifySquenceOfBST(sequence, start, i - 1);
    		}
    		
    		// 判断左子树是不是二叉搜索树
    		boolean right = true;
    		if(i < end){
    			left = verifySquenceOfBST(sequence, i, end - 1);
    		}
    		// 两个都为true时，才返回true
    		return (left && right);
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		
    		LastSequenceOfTree tree = new LastSequenceOfTree();
    		
    		int[] sequence = {5, 7, 6, 9, 11, 10, 8};
    		boolean result = tree.verifySquenceOfBST(sequence, 0, sequence.length - 1);
    		System.out.println(result);   // true
    		
    		int[] sequence1 = {7, 4, 6, 5};
    		boolean result1 = tree.verifySquenceOfBST(sequence1, 0, sequence1.length - 1);
    		System.out.println(result1);   // false
    		
    	}
    }

上面的答案是来自于《剑指Offer》中的思路。这里再给出牛客网中的一种答案，整体思路是一样的，只不过代码书写格式不同而已。

package com.zju.offer.tree;
    
    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
     * 如果是则返回 true，否则返回 false。
     * 假设输入的数组的任意两个数字都互不相同。
     * 
     * 思路：找住二叉查找树的特点：左子树 < 根 <= 右子树  使用分治思想
     */
    public class LastSequenceOfTree_Method2 {
    
    	public boolean verifySeqenceOfBST(int[] sequence){
    		if(sequence.length == 0){
    			return false;
    		}
    		if(sequence.length == 1){
    			return true;
    		}
    		
    		return judge(sequence, 0, sequence.length - 1);
    	}
    
    	private boolean judge(int[] arr, int start, int end) {
    		// 递归终止条件
    		if(start >= end){
    			return true;
    		}
    		
    		int i = start;
    		// 找到左子树节点的个数：i-1
    		while(arr[i] < arr[end]){
    			++i;
    		}
    		for(int j = i; j < end; j++){
    			// 右子树的节点值不能小于根节点
    			if(arr[j] < arr[end]){
    				return false;
    			}
    		}
    		
    		// 沿左右子树分别递归
    		return judge(arr, start, i - 1) && judge(arr, i, end - 1);
    	}
    }

[https_blog.csdn.net_jsqfengbao_article_details_47281789]: https://blog.csdn.net/jsqfengbao/article/details/47281789
[2019010815504820.png]: /images/20220329/290c2c16ec8f40e88b59f7d84f885724.png