二叉搜索树后序遍历

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树

后序遍历的访问顺序:左子树,右子树,根节点。

思路:根节点位于最后一位,根据左子树节点均小于根节点,右子树均大于根节点,可以确定左右子树的范围,递归遍历即可。

public class Solution { 
     static boolean VerifySquenceOfBST(int [] sequence) { 
         if(sequence.length==0)return false;
         return DFS(sequence,0,sequence.length-1);
    }
    static  boolean DFS(int[] sequence,int left,int right){ 
        if(left==right)return true;   //边界
        int root=sequence[right];
        int numLeft=-1;
        for(int i=left;i<right;i++){ 
            if(sequence[i]>root){ 
                numLeft=i;           //第一个比根节点大的
                break;
            }
        }
        if(numLeft!=-1){ 
            for(int i=numLeft+1;i<right;i++){ 
            if(sequence[i]<root)return  false;    //判断是否还有小的,若有显然不对
            }
        }
        if(numLeft==-1){                    //全是左子树,所有节点都比根节点小
            numLeft=left;
        }

        //递归,条件表达式处理的单个元素问题
        return  DFS(sequence,left,numLeft)&&DFS(sequence,numLeft,right-1);
    }
}
    原文作者:北风扬尘尘飞扬
    原文地址: https://blog.csdn.net/weixin_45458665/article/details/102942937
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞