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

2年前 (2022) 程序员胖胖胖虎阿
251 0 0

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

解决思路

根据后序遍历的性质,最后一个元素就是二叉搜索树的根结点。而二叉搜索树按中序遍历得出的序列又是递增有序的,从根结点可以将序列分为两段:前一段(左子树)都比根结点小,后一段(右子树)都比根结点大。

因此我们知道:该后序遍历结果序列中,所有小于根结点的都是其左子树的结点,而大于根结点的就是其有子树的结点,并且各自是连续的。如果条件不满足,则返回 false

public class Solution {
    
    public boolean VerifySquenceOfBST(int[] sequence) {
        if(sequence.length == 0) {
            return false;
        }
        return judge(sequence, 0, sequence.length - 1);
    }
    
    public boolean judge(int[] sequence, int start, int end) {
    	// 比较完成,则返回 true
        if(start >= end) {
            return true;
        }
        // 这里的值必须是 end,否则会出现空指针异常
        int index = end;
        // 找到分界点
        while(index > start && sequence[index - 1] > sequence[end]) {
            index--;
        }
        // 判断分界点前是否有不满足的数存在
        for(int i = index - 1; i >= start; i--) {
            if(sequence[i] > sequence[end]) {
                return false;
            }
        }
        return judge(sequence, start, index - 1) && judge(sequence, index, end - 1);
    }
}

版权声明:程序员胖胖胖虎阿 发表于 2022年10月13日 下午12:08。
转载请注明:二叉搜索树的后序遍历序列 | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...