判断一个数组是不是某二叉搜索树的后序遍历的结果

---恢复内容开始---

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

判断一个数组是否是二叉查找树的后序遍历的结果首先要知道二叉查找树的后序遍历是怎么样的。

二叉查找树的特点：在除了叶子节点之外的其它节点中，节点的左子树的任意一个数不大于这个节点，右子树的任意一个数不小于这个节点。

二叉树的后序遍历：对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。

递归判断T是不是都是二叉树的后序遍历。

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verifySquenceOfBST(sequence, 0, sequence.length - 1);
    }
 
    boolean verifySquenceOfBST(int[] sequence, int start, int end) {
        if (start == end) {
            return true;
        }
        int key = sequence[end];
        int i = start;
        for (; i < end; i++) {
            if (sequence[i] > key) {//找到比最后一个元素大的第一个元素，确认这个T的左子树和右子树
                break;
            }
        }
        int m = i;
        for (; i < end; i++) {
            if (sequence[i] < key) {//如果右子树中是否有比最后一个元素小的元素，返回false
                return false;
            }
        }
        if (m == start || m == end) {//所有元素都比最后一个元素小的情况，即这个序列T只有左子树，此时继续判断它的左子树。 第一个元素比最后一个元素大时，同理，
//继续判断它的右子树
            return verifySquenceOfBST(sequence, start, end - 1);
        } else {
            return verifySquenceOfBST(sequence, start, m - 1) && verifySquenceOfBST(sequence, m, end - 1);
        }
    }
    
}

判断一个数组是不是某二叉搜索树的后序遍历的结果

相关推荐