题目

如题。

题解

从序列第一个大于根节点的值往后都是右子树，判断右子树是否都大于根节点。

然后递归判断左右子树是否是BST

代码

class TreeNode {

	int val = 0;

	TreeNode left = null;

	TreeNode right = null;

	public TreeNode(int val) {

		this.val = val;

	}

}

public class VerifySeqOfBST {

	public static void main(String[] args) {

		//test case

		int[] seq= {1,2,4,3};

		boolean tag=varifySeqBST(seq,0,seq.length);//

		System.out.print(tag);

	}

	public static boolean varifySeqBST(int[] seq,int beg,int end) {

		if(seq==null) {

			return false;

		}

		int rootVal=seq[end-1];

		//找到右子树开始的位置

		int pos=end;

		for(int i=beg;i<end-1;++i) {

			if(seq[i]>rootVal) {

				pos=i;

				break;

			}

		}

		//检查右子树

		for(int i=pos;i<end-1;++i) {

			if(seq[i]<rootVal) {//

				return false;

			}

		}

		//判断左右子树内部是否是BST

		boolean leftBST=true;

		if(pos>beg&&pos!=end) {//

			leftBST=varifySeqBST(seq,beg,pos);

		}

		boolean rightBST=true;

		if(pos<end-1) {

			rightBST=varifySeqBST(seq,pos,end-1);//刨去根节点

		}

		return leftBST&rightBST;

	}

}

代码第二遍写

public class Solution {

    public boolean VerifySquenceOfBST(int [] sequence) {

        if(sequence==null||sequence.length==0){

            return false;

        }

        return judgeBST(sequence,0,sequence.length-1);

    }

    private boolean judgeBST(int[] sequence,int l,int r){

        if(l==r-1||l==r){

            return true;

        }

        int rootVal=sequence[r];

        int rPos=l;

        for(;sequence[rPos]<rootVal;++rPos){

        }

        for(int i=rPos;i<r;++i){

            if(sequence[i]<rootVal){

                return false;

            }

        }

        boolean left=true;

        if(rPos>l){

            left=judgeBST(sequence,l,rPos-1);

        }

        boolean right=true;

        if(rPos<r){

            right=judgeBST(sequence,rPos,r-1);

        }

        return left&&right;

    }

}