首页 > 试题广场 > 二叉搜索树的后序遍历序列
[编程题]二叉搜索树的后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
推荐
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 回复(125)
/*
//递归
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 回复(93)
python:后序遍历 的序列中,最后一个数字是树的根节点 ,数组中前面的数字可以分为两部分:第一部分是左子树节点 的值,都比根节点的值小;第二部分 是右子树 节点的值,都比 根 节点 的值大,后面用递归分别判断前后两部分 是否 符合以上原则
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if sequence==None or len(sequence)==0:
            return False
        length=len(sequence)
        root=sequence[length-1]
        # 在二叉搜索 树中 左子树节点小于根节点
        for i in range(length):
            if sequence[i]>root:
                break
        # 二叉搜索树中右子树的节点都大于根节点
        for j  in range(i,length):
            if sequence[j]<root:
                return False
        # 判断左子树是否为二叉树
        left=True
        if  i>0:
            left=self.VerifySquenceOfBST(sequence[0:i])
        # 判断 右子树是否为二叉树
        right=True
        if i<length-1:
            right=self.VerifySquenceOfBST(sequence[i:-1])
        return left and right

发表于 2017-11-07 19:42:32 回复(13)
思路:
已知条件后序序列最后一个值为root;二叉搜索树左子树值都比root小,右子树值都比root大。
1、确定root;
2、遍历序列(除去root结点),找到第一个大于root的位置,则该位置左边为左子树,右边为右子树;
3、遍历右子树,若发现有小于root的值,则直接返回false;
4、分别判断左子树和右子树是否仍是二叉搜索树(即递归步骤1、2、3)。
参考代码(不够精简,只为理清思路):
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
		vector<int> leftTree,rightTree;
        int root; // 根结点
        if(sequence.empty()) return false;
        int index = 0; // 标记左右子树界限
        int len = sequence.size();
        root = sequence[len-1];
        int i=0;
        for(;i<len-1;++i)
        {
            if(sequence[i]>root) break; // 找到第一个大于根结点的位置,则左边为左子树,右边为右子树
        }
        for(int j=i;j<len-1;++j) // 循环时去除root,因此为len-1
        {
            if(sequence[j]<root) return false; // 有一个小于root,则返回false
        }
        
        if(i!=0)
        {
            // 即有左子树
            for(int m=0;m<i;++m)
            {
                leftTree.push_back(sequence[m]);
            }
        }
        if(i!=len-2)
        {
            for(int j=i;j<len-1;++j)
            {
                rightTree.push_back(sequence[j]);
            }
        }
        
        bool left = true,right = true; // 看左右子树是否是二叉搜索树
        if(leftTree.size()>1) VerifySquenceOfBST(leftTree);
        if(rightTree.size()>1) VerifySquenceOfBST(rightTree);
        
        return (left&&right);
    }
};
发表于 2016-08-22 15:31:35 回复(18)
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;
        if(sequence.length==1)
            return true;
        return ju(sequence, 0, sequence.length-1);
        
    }
    
    public boolean ju(int[] a,int star,int root){
    	if(star>=root)
    		return true;
    	int i = root;
        //从后面开始找
    	while(i>star&&a[i-1]>a[root])
    		i--;//找到比根小的坐标
        //从前面开始找 star到i-1应该比根小
    	for(int j = star;j<i-1;j++)
    		if(a[j]>a[root])
    			return false;;
        return ju(a,star,i-1)&&ju(a, i, root-1);
    }
}

发表于 2016-04-15 22:18:04 回复(32)
思路:找住二叉查找树的特点:左子树<根<=右子树  使用分治思想
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 回复(23)
采用分治法的思想,找到根结点、左子树的序列、右子树的序列,分别判断左右子序列是否为二叉树的后序序列。

由题意可得:
1. 后序遍历序列的最后一个元素为二叉树的根节点;
2. 二叉搜索树左子树上所有的结点均小于根结点、右子树所有的结点均大于根结点。

算法步骤如下:
1. 找到根结点;
2. 遍历序列,找到第一个大于等于根结点的元素i,则i左侧为左子树、i右侧为右子树;
3. 我们已经知道i左侧所有元素均小于根结点,那么再依次遍历右侧,看是否所有元素均大于根结点;若出现小于根结点的元素,则直接返回false;若右侧全都大于根结点,则:
4. 分别递归判断左/右子序列是否为后序序列;

public boolean VerifySquenceOfBST(int [] sequence) {
    if ( sequence==null || sequence.length<=0 ) return false;
    return VerifySquenceOfBST(sequence, 0, sequence.length-1);
}

private boolean VerifySquenceOfBST(int [] sequence, int start, int end){
    if ( start>=end ) 
        return true;
    
    int root = sequence[end];
    
    int i=start;
    while( sequence[i] < root ){
        i++;
    }
    
    int j=i;
    while( j<end ){
        if ( sequence[j]<root ) {
            return false;
        }
        j++;
    }
    
    boolean left = VerifySquenceOfBST(sequence, start, i-1);
    boolean right = VerifySquenceOfBST(sequence, i, end-1);
    return left && right;
}

发表于 2017-04-13 15:54:08 回复(9)

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)
/**
 * 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 回复(6)
思路:二叉搜索树的合法后序序列是: 对于序列的最后一个结点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)
递归遍历
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 回复(1)
一个非常规方法,看了半天没看到一样的,提供一个新思路。
前面有道题是“栈的压入、弹出序列”。
写这道题的例子时发现二叉树的中序序列和后序序列就满足栈的压入弹出序列关系。
即如果把中序序列当做栈的压入序列,那么后序序列是该栈的一个弹出序列。
而BST的中序是排序数组。因此将本题的序列排序作为中序序列,引用前面题的答案判断两序列是否满足上述关系即可。
import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public boolean VerifySquenceOfBST(int [] seq) {
        int[] arr = seq.clone();
        Arrays.sort(arr);
        return IsPopOrder(arr,seq);
        
    }
    
//判断第二个序列是否可能为第一个序列的弹出顺序,引用的“栈的压入、弹出序列”题目的答案
public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack<Integer> s = new Stack<Integer>();
        //用于标识弹出序列的位置
        int popIndex = 0;
        for(int i = 0; i< pushA.length;i++){
            s.push(pushA[i]);
            //如果栈不为空,且栈顶元素等于弹出序列
            while(!s.empty() &&s.peek() == popA[popIndex]){
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}

发表于 2019-06-27 15:20:08 回复(1)

递归是个好东西

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)
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)
# -*- 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 回复(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 回复(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)
以[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)
# -*- 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 回复(1)