首页 > 试题广场 >

二叉搜索树的后序遍历序列

[编程题]二叉搜索树的后序遍历序列
  • 热度指数:869559 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围: 节点数量 ,节点上的值满足 ,保证节点上的值各不相同
要求:空间复杂度 ,时间时间复杂度
提示:
1.二叉搜索树是指父亲节点大于左子树中的全部节点,但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
4.参考下面的二叉搜索树,示例 1

示例1

输入

[1,3,2]

输出

true

说明

是上图的后序遍历 ,返回true         
示例2

输入

[3,1,2]

输出

false

说明

不属于上图的后序遍历,从另外的二叉搜索树也不能后序遍历出该序列 ,因为最后的2一定是根节点,前面一定是孩子节点,可能是左孩子,右孩子,根节点,也可能是全左孩子,根节点,也可能是全右孩子,根节点,但是[3,1,2]的组合都不能满足这些情况,故返回false    
示例3

输入

[5,7,6,9,11,10,8]

输出

true
推荐
BST的后序序列的合法序列是,对于一个序列S,最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。完美的递归定义 : ) 。

class Solution {
    bool judge(vector<int>& a, int l, int r){
        if(l >= r) return true;
        int i = r;
        while(i > l && a[i - 1] > a[r]) --i;
        for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false;
        return judge(a, l, i - 1) && (judge(a, i, r - 1));
    }
public:
    bool VerifySquenceOfBST(vector<int> a) {
        if(!a.size()) return false;
		return judge(a, 0, a.size() - 1);
    }
};

编辑于 2015-09-24 10:51:14 回复(148)
思路:找住二叉查找树的特点:左子树<根<=右子树  使用分治思想
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){
            return false;
        }
        if(sequence.length == 1){
            return true;
        }
        return judge(sequence,0,sequence.length-1);
    }
    
    public boolean judge(int[] a,int start,int end){
        if(start >= end){
            return true;
        }
        int i = start;
        while(a[i] < a[end]){
            ++i;
        }
        for(int j=i;j<end;j++){
            if(a[j] < a[end]){
                return false;
            }
        }
        return judge(a,start,i-1) && judge(a,i,end-1);
    }
}

发表于 2016-11-22 16:28:48 回复(25)

bool VerifySquenceOfBST(vector<int> sequence) {

    int n=sequence.size();

    int i=0;

    if (n==0) {

        returnfalse;

    }

    while (--n) {

        while(sequence[i]<sequence[n]) i++;

        while (sequence[i]>sequence[n]) i++;

        if (i<n) return false;

        i=0;

    }

    returntrue;

}

发表于 2015-08-24 00:00:21 回复(50)
/* 思路清晰的代码 -- 递归方式 */
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) 
    {
        if(sequence.empty()) return false;
        
        int root = sequence[sequence.size()-1]; // 找到根节点
        
        // 在二叉搜索树中左子树的结点小于根节点
        vector<int> leftSequence;
        int i = 0;
        for(i = 0;i<sequence.size()-1;i++){
            if(sequence[i] < root)
                leftSequence.push_back(sequence[i]);
            else
                break;
        }
        
        // 在二叉搜索树中右子树的结点大于根节点
        vector<int> rightSequence;
        for(int j = i;j<sequence.size()-1;j++){
            if(sequence[j] > root)
                rightSequence.push_back(sequence[j]);
            else
                return false;
        }
        
        // 如果左子树不为空,则判断左子树是否满足
        bool left = true;
        if(!leftSequence.empty())
            left = VerifySquenceOfBST(leftSequence);
        // 如果右子树不为空,则判断右子树是否满足
        bool right = true;
        if(!rightSequence.empty())
            right = VerifySquenceOfBST(rightSequence);
        
        return (left&&right);        
    }
};

/* 非递归方式 注:该代码抄袭于x楼(作者:SevenYears),感觉无论是代码还是思路都挺好,便引了过来,学习了!
 非递归也是一个基于递归的思想:
左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,right部分的
最后一个数字是右子树的根他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件
即可,即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理
对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树只需看看右子树的右子树是否符合要求即可 */ class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { int size = sequence.size(); if(0 == size) return false; int i = 0; while(--size){ while(sequence[i++] < sequence[size]); while(sequence[i++] > sequence[size]); if(i < size) return false; i = 0; } return true; } };
发表于 2017-04-10 20:58:19 回复(4)
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        
        return self.helper(sequence)
    
    # 增加helper函数是因为对于递归来说sequence为空可以作为终止条件,而对于判断BST而言 sequence为空是False
    def helper(self, sequence):
        if not sequence:
            return True
        
        root = sequence[-1]
        for i in range(len(sequence)):
            if sequence[i] > root:
                break
                
        for right in sequence[i:-1]:
            if right < root:
                return False
            
        return self.helper(sequence[:i]) and self.helper(sequence[i:-1])

发表于 2018-07-05 21:16:08 回复(4)
递归遍历
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        
        if(sequence == null || sequence.length == 0){
            return false;
        }
        if(sequence.length == 1){
            return true;
        }
        return search(sequence,0,sequence.length-1);
    }
    
    public boolean search(int [] seq , int start, int end ){
        
        //遍历完数组的一部分,没报错,返回true
        if(start > end ){
            return true;
        }
        int i = end;
        //i从最后往前倒,一直找到第一个比当前根节点小的数,从这个数开始将字符串分为前后两部分
        while(i>start && seq[i-1] > seq[end]){
            i--;
        } 
        //前办部门如果有比根节点大的数,返回false
        for(int j=0;j<i-1;j++){
        	if(seq[j] > seq[end]){
                return false;
            }                
        }
        //遍历数组的前半部分和后半部分
        return  search(seq,start,i-1)&&search(seq,i,end-1);
        
        
        
    }
    
}

编辑于 2016-08-26 22:56:31 回复(3)
/**
 * T: 二叉搜索树的后序遍历序列
 * 
 * 题目描述 
 * 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 * 
 * date: 2015.11.28  10:43
 * @author SSS
 *
 */
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
		if (sequence == null || sequence.length == 0) {
			return false;
		}
		
        boolean flag = this.isBST(sequence, 0, sequence.length - 1);
        
        return flag;
    }
	
	/**
	 * 递归实现检测
	 * 
	 * 对于后序遍历来说,序列数组的最后一个元素一定是根节点,
	 * 则根据这个元素,将前面的数组分为左、右两个部分,左侧部分都小,右侧部分都大,
	 * 如果右侧部分有比该根节点小的元素,那么就不是后序遍历,如此递归进行
	 * @param arr
	 * @param start
	 * @param end
	 * @return
	 */
	public boolean isBST(int []arr, int start, int end) {
		if (start >= end) {
			return true;
		}
		
		// 当前数组(从start到end部分)的根节点
		int curElement = arr[end];
		int splitIndex;
		// 找到比curElement大和比curElement小的分界点,分成左侧、右侧两组数据
		for(splitIndex = start; splitIndex < end && arr[splitIndex] < curElement;splitIndex ++);
		
		// 只需要看右侧即可,因为前面的for循环,已经确保左侧部分全部都小于curElement
		for (int i = splitIndex; i < end; i++) {
			if (arr[i] < curElement) {
				return false;
			}
		}
		
		return isBST(arr, start, splitIndex - 1) && isBST(arr, splitIndex, end - 1);
	}
}
编辑于 2015-11-28 11:42:38 回复(7)
思路:二叉搜索树的合法后序序列是: 对于序列的最后一个结点T是树的根结点,根据T可以把剩余结点分为两部分,前部分都比T小,后部分都比T大,这两部分都是合法的后序序列

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        
        root = sequence[-1]
        
        # 在二叉搜索中左子树的结点小于跟结点
        i = 0
        for node in sequence[:-1]:
            if node > root:
                break
            i += 1
            
        # 在二叉搜索中右子树的结点小于跟结点
        for node in sequence[i:-1]:
            if node < root:
                return False
            
        # 判断左子树是不是二叉搜索树
        left = True
        if i > 1:
            left = self.VerifySquenceOfBST(sequence[:i])
        
        right = True
        if i < len(sequence) - 2 and left:
            right = self.VerifySquenceOfBST(sequence[i+1:-1])
        
        return left and right

发表于 2016-07-25 15:55:13 回复(1)
import java.util.Arrays;
public class Solution {
   public static boolean VerifySquenceOfBST(int[] sequence) {
        if(sequence==null||sequence.length==0)
            return false;
        int root=sequence[sequence.length-1];
        int i=0;
        for(;i<sequence.length-1;i++){
            if(sequence[i]>root){
                break;
            }
        }
        int j=i;
        for(;j<sequence.length-1;j++){
            if(sequence[j]<root)
                return false;
        }
        boolean left=true;
        boolean right=true;
        if(i>0){
            left=VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
        }
        if(i<sequence.length-1)
            right=VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length-1));
        return (left&&right);

    }
}


发表于 2015-04-22 16:17:53 回复(7)
class Solution:
    def VerifySquenceOfBST(self, sequence):
        size = len(sequence)
        if size == 0:
            return False
        size -= 1
        index = 0
        while size:
            while index < size and sequence[index] < sequence[size]:
                index += 1
            while index < size and sequence[index] > sequence[size]:
                index += 1
            if index < size:
                return False
            index = 0
            size -= 1
        return True
编辑于 2018-10-21 10:45:40 回复(3)
以[4, 8, 6, 12, 16, 14, 10]为例,首先最右边的元素10为根,然后从后往前找到大于根的一个连续序列[12, 16, 14](即右子树),为了区分左右子树,这个查找过程是必须的。但没必要遍历左子树,因为我们可以在递归函数中加一个参数来记录根的值,以限制左子树部分的上限,这样每次可以减少一半的遍历。为什么不用限制它的右子树的下限呢?因为我们在上述找右子树的过程中已经保证了右子树中的结点都大于根。
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return valid(sequence, 0, sequence.length-1, 0x7fffffff);
    }
    
    private boolean valid(int[] sequence, int start, int end, int max) {
        if (start > end) {
            return true;
        }
        int root = sequence[end];
        if (root > max) {
            return false;
        }
        int i = end;
        for (; i - 1 >= start && sequence[i - 1] > root; i--);
        return valid(sequence, start, i-1, root) && valid(sequence, i, end-1, max);
    }
}

发表于 2018-01-11 15:25:52 回复(0)

python solution:

根据最后一个数把序列分成左右两个部分,如果左部分全部小于该数,右部分全部大于该数。则证明是后序遍历。根据这个思路,递归即可。

使用了bisect来把序列分成两个部分。

这个解法有点冗余。。凑合着看吧

import bisect


class Solution:
    def VerifySquenceOfBST(self, sequence):
        if not sequence:
            return False

        def verify(sequence):
            if not sequence:
                return True
            pos = bisect.bisect_right(sequence[:-1], sequence[-1])
            left, right = sequence[:pos], sequence[pos:-1]
            for i in left:
                if i > sequence[-1]:
                    return False
            for i in right:
                if i < sequence[-1]:
                    return False
            return verify(left) and verify(right)

        return verify(sequence)
发表于 2017-10-21 13:34:26 回复(5)

递归是个好东西

class Solution {
public:
    bool fun(vector<int> s){
        if(!s.size()) return true;
        int root = s[s.size()-1], i = 0;
        while(s[i] < root) i++;
        for(int j = i; j < s.size(); j++) if(s[j] < root) return false;
        return fun(vector<int> (s.begin(), s.begin()+i))&&
            fun(vector<int> (s.begin()+i, s.end()-1));
    }


    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        return fun(sequence);
    }
};
编辑于 2018-12-03 11:00:27 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        root=sequence[-1]
        for i in range(len(sequence)):
            if sequence[i]>root:
                break
        for j in range(i,len(sequence)):
            if sequence[j]<root:
                return False
        left=right=True
        if i>1:
            left=self.VerifySquenceOfBST(sequence[0:i])
        if i<len(sequence)-1:
            right=self.VerifySquenceOfBST(sequence[i:-1])
        return left and right

发表于 2018-09-18 13:12:01 回复(3)
# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        if sequence == []:
            return False
        if len(sequence) == 1 or len(sequence) == 2:
            return True
        else:
            root = sequence.pop(-1)
            sign = 0
            for i in range(len(sequence)):
                if sequence[i] > root:
                    sign = 1
                if (sign == 1) and (sequence[i] < root):
                    return False
            return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:])
        # write code here

编辑于 2018-04-03 18:34:23 回复(6)
非递归的方法,不关心谁是左子树,谁是右子树
命题1:每个节点root的leftTree < root < rightTree --->用递归做,不不解释
命题2,:所有的左节点都<root<所有的右边节点
等价命题:命题1 <==>命题2
只需要找到第一个比root = sequence[len]大的数,就是他的右节点,确保root <right即可
  public static boolean VerifySquenceOfBST(int [] sequence) {
        //鲁棒性
        if(sequence == null || sequence.length <= 0) return false;
        if(sequence.length == 1) return true;
        int len = sequence.length;
        int i = 0;
        while(--len > 0) {//满足每个root 左边的节点 < root,右边的节点>root
            while(sequence[i] < sequence[len]) ++i;//i指向右子树的根节点
            while(sequence[i] > sequence[len]) ++i;//计算右子树的个数(右子树全部大于root)
            if(i < len) return false; //若满足命题2的条件,那么i == len 
            i = 0;//重置计数器
        }
        return true;
    }

编辑于 2018-06-14 10:25:40 回复(0)
二叉搜索树的后序遍历判断:
1、首先明白二叉搜索树的特点,左节点小于根,右节点大于根,左右子树也同样是二叉搜索树
2、根据二叉搜索树的特点,我们发现需要递归的判断,根节点肯定在数组的末尾
3、找出比根节点小的就是左子树,找到比根节点大的就是右子树
4、如果左右子树中有不满足的条件的元素则返回或者结束判断
5、直到所有元素都判断完则满足二叉搜索树的特点,或者中途返回

**这里需要特别注意的是,要判定数组为空的情况,故将递归函数单独拿出


class Solution {
public:
    bool isBTree(vector<int> sequence,int l,int r)
    {
        if(r <= l)
            return true;
        
        //左子树都小于根节点
        int i=l;
        for( ;i<r;i++)
        {
            if(sequence[i]>sequence[r])
            {
                break;//不满足左子树条件则跳出
            }
        }
        //右子树都大于根节点
        for(int j=i;j<r;j++)
        {
            if(sequence[j]<sequence[r])
            {
                return false;//不满足右子树条件返回false
            }
        }
        return isBTree(sequence,l,i-1) && isBTree(sequence,i,r-1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(0 >= sequence.size())
            return false;
        return isBTree(sequence,0,sequence.size()-1);
    }
};

发表于 2018-03-24 17:37:56 回复(0)
/*
//递归
class Solution {
public:
	bool VerifySquenceOfBST(vector<int> sequence) {

		int size = sequence.size();
		if(0==size)
		{
			return false;
		}

		return isLastOrder(sequence, 0, size-1);
	}

private:
	bool isLastOrder(vector<int>& sequece, int b, int e)
	{
		if(b==e)
		{
			return true;
		}
		int mid = b;
		while(sequece[mid++]<sequece[e] && mid<e);

		int tmp = mid;
		while (sequece[tmp++]>sequece[e] && tmp<e);
		if(tmp<e)
		{
			return false;
		}

		if(mid==b || mid==e)
		{
			return isLastOrder(sequece, b, e-1);
		}
		else 
		{
			return (isLastOrder(sequece, b, mid-1) && isLastOrder(sequece, mid, e-1));
		}
	}
};*/

//非递归  
//非递归也是一个基于递归的思想:
//左子树一定比右子树小,因此去掉根后,数字分为left,right两部分,right部分的
//最后一个数字是右子树的根他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件
//即可,即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理

//对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
//只需看看右子树的右子树是否符合要求即可
class Solution {
public:
	bool VerifySquenceOfBST(vector<int> sequence) {
		int size = sequence.size();
		if(0==size)return false;

		int i = 0;
		while(--size)
		{
			while(sequence[i++]<sequence[size]);
			while(sequence[i++]>sequence[size]);

			if(i<size)return false;
			i=0;
		}
        return true;
	}
};

发表于 2015-09-09 22:00:53 回复(117)
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) {
            return false;
        }
        return VerifySquenceOfBSTCore(sequence, 0, sequence.length - 1);
    }
    private boolean VerifySquenceOfBSTCore(int[] sequence, int start, int end) {
        //在不断查找过程中,区域不断缩小,为空时,证明之前的所有范围都满足检测条件
        // 也就是是一个BST
        if (start >= end) {
            return true;
        }
        //拿到root节点的值
        int root = sequence[end];
        //先遍历左半部分,也就是整体都要比root小,拿到左子树序列
        int i = start;
        while (i < end && sequence[i] < root) {
            i++;
        }
        //在检测右子树是否符合大于root的条件,要从i开始,也就是右半部分的开始
        for (int j = i; j < end; j++) {
            if (sequence[j] < root){
                return false;
            }
        }
        //走到这里,就说明,当前序列满足需求。但并不代表题目被解决了,还要在检测left和right各自是否也满 足
        return VerifySquenceOfBSTCore(sequence,start,i-1) && VerifySquenceOfBSTCore(sequence,i,end-1);
    }
}

发表于 2022-05-26 13:28:07 回复(0)

序列最后一位为根节点
递归判断左右子树的合法性

    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        root = sequence[-1]
        valid = False # 到达右子树的标志
        tar = -1 # 左子树的范围
        for i,_ in enumerate(sequence[:-1]):
            if _ > root: # 右子树部分
                valid = True
            elif valid: # 在右子树出现比root小的树
                return False
            else: # 左子树部分
                tar = i
        left = True if tar == -1 else self.VerifySquenceOfBST(sequence[:tar+1])
        right = True if not valid else self.VerifySquenceOfBST(sequence[tar+1:-1])
        return left and right
发表于 2019-06-13 16:52:04 回复(0)
使用递归求解
//import java.util.ArrayList;
public class Solution {
    //public boolean res = true;
    public boolean VerifySquenceOfBST(int [] sequence) {
        //ArrayList<Integer> arr = new ArrayList<Integer>();
        if (sequence.length == 0) {
            return false;
        }
        if (sequence.length == 1) {
            return true;
        }
        return bs(sequence, 0, sequence.length - 1);
    }
    
    public boolean bs(int [] arr, int start, int end) {
        if (start >= end) {
            return true;
        }
        int j = end - 1;
        while (j >= start) {
            if (arr[j] < arr[end]) {
                break;
            }
            j--;
        }
        if (j < 0) {
            return true;
        }
        for (int i = j; i >= start; i--) {
            if (arr[i] > arr[end]) {
                return false;
            }
        }
        return bs(arr, 0, j) && bs(arr, j + 1, end - 1);
    }
}

发表于 2018-07-13 23:47:52 回复(0)