【剑指offer-Java版】24二叉搜索树后序遍历序列

迈不过友情╰ 2022-08-21 09:40 111阅读 0赞

二叉搜索树的后续遍历序列：既然是二叉搜索树，那么就满足左子树结点都大于或者小于根节点右子树都小于或大于根结点

根据搜索树的这种特点，将给定的树划分为左子树或者右子树，递归的处理左右子树

public class _Q24 {
    
        public boolean VerifySeqOfBST(int seq[]){
            if(seq == null ) return false;
    
            if(seq.length == 1 || seq.length == 0) return true;
    
            boolean result = true;
            int index = 0;
    
            // 以index来区分左右子树 - index左边是左子树，以index开始至根结点是右子树
            for (int i = 0; i < seq.length; i++) {
                // 题目申明是没有重复元素的，那么第一个大于根结点值的就是右子树中的第一个结点
                if (seq[i] > seq[seq.length - 1]) { 
                    index = i;
                    break;
                }
            }
    
            // 判断右子树是否满足关系-右子树必须都大于根结点
            for(int i=index; i<(seq.length-1); i++){
                if(seq[i] < seq[seq.length - 1]){
                    result = false;
                    break;
                }
            }
    
            // 递归的判断左子树
            if(result == true){
                result = VerifySeqOfBST(Arrays.copyOfRange(seq, 0, index));
            }
    
            // 递归的判断右子树
            if(result == true){
                result = VerifySeqOfBST(Arrays.copyOfRange(seq, index, seq.length-1));
            }
    
            return result;
        }
        }

测试代码：

public class _Q24Test extends TestCase {
        
    
        _Q24 verifyTree = new _Q24();
    
        public void test(){
            int seq1[] = {
       5, 7, 6, 9, 11, 10, 8};
            int seq2[] = {
       7, 4, 6, 5};
            int seq3[] = {
       5};
            int seq4[] = {};
            int seq5[] = null;
    
            System.out.println(verifyTree.VerifySeqOfBST(seq1));
            System.out.println(verifyTree.VerifySeqOfBST(seq2));
            System.out.println(verifyTree.VerifySeqOfBST(seq3));
            System.out.println(verifyTree.VerifySeqOfBST(seq4));
            System.out.println(verifyTree.VerifySeqOfBST(seq5));
        }
        }