WXGZH

每日一道算法 欢迎关注 WXGZH：小夕学算法

题目

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

参考以下这颗二叉搜索树：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

• 运用递归的思路来不断的判断子树是否是一颗二叉搜索树,运用二叉搜索树的性质:左子树的节点值比根节点的小,右子树的节点值比根节点的大;在一个后续遍历的序列中,位于序列最后的元素是根节点

• 所以可以总结出一个后序序列可划分成['左子树','右子树','根节点']这三部分组成,顺序是严格的
  好了,有了上面的特性,我们使用一个例子进行分析:

  
  
• 划分左子树,我们能知道现在这个树的根节点为[5],从头开始遍历节点,直到我们遇到比根节点大的或者根节点,之前那些比根节点小的值是左子树的节点,此树的左子树序列为[1]
• 划分右子树,可以看到当遍历到6的时候,6>5,按照上面总结的规律,说明6之后到根节点的序列都应该是右子树,即[6,3,2],这是就需要判断下是否在右子树的序列中存在比根节点小的元素,如果有的话就说明是不符合条件的,显然[3,2]都是比[5]要小的,不符合条件
• 如果不存在在右子树中比根节点小的元素,递归的遍历上述左右子树

代码

Java

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur(int [] postorder, int i, int j) {
        if (i >= j) return true;
        int m = i;
        while(postorder[i] < postorder[j]) i++; // 小于j的都是左子树 j是根节点 根据二叉搜索树的性质
        int p = i; // 有可能是右子树开头的第一个节点
        while(postorder[i] > postorder[j]) i++;
        if (i != j) return false; // 如果是正常的后序遍历序列  必然相等
        return recur(postorder, m , p -1) && recur(postorder, p , j - 1);
    }
}

C++

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.empty()) return true;
        int len = postorder.size();
        return recursion(postorder, 0, len - 1);
    }
    bool recursion(vector<int>& postorder, int left, int right)
    {
        if(left >= right) return true; // 没有左子树（比如[5,4,3,2,1]），true
        int root = postorder[right];
        int pos = left; // 必须要设置一个 pos 变量保存 left，不能直接操作 left！
        for(; pos<right; ++pos)
        {
            // 找到右子树起点
            if(postorder[pos] > root) break;
        }
        for(int j=pos; j<right; ++j)
        {
            // 如果右子树部分有小于 root 的，false
            if(postorder[j] < root) return false;
        }
        // 看左子树是否也是后序遍历。如果前面不设置 pos 的话，这里就会是 (postorder,0,left-1)，会严重超时
        if(!recursion(postorder, left, pos - 1)) return false; 
        if(!recursion(postorder, pos, right - 1)) return false;// 看右子树是否也是后序遍历
        return true;
    }
};

Python

class Solution(object):
    def verifyPostorder(self, postorder):
        """
        :type postorder: List[int]
        :rtype: bool
        """
        if not postorder:
            return True
        def isTree(postorder):
            root = postorder[-1]
            length = len(postorder)
            for i in range(length): # 找到左子树的区间,此时注意下这样的切分不可能出现左子树中的节点比根节点大
                if postorder[i] > root:
                    break
            
            for j in range(i, length-1):# 如果右子树中存在比根节点的小的值,那么是不符合条件的
                if postorder[j] < root:
                    return False

            left = True
            if i > 0:
                left = isTree(postorder[:i])#判断左子树是否符合条件
            right = True
            if i < length -1 :
                right = isTree(postorder[i:-1])#判断右子树是否符合条件
            return left and right
        return isTree(postorder)

JS

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function (postorder) {
    let len = postorder.length;
    // 若为叶子节点，则返回 true
    if (len < 2) return true
    // 后序遍历的最后一个元素为根节点
    let root = postorder[len - 1];
    let i = 0
    // 划分左/右子树
    for (; i < len - 1; i++) {
        if (postorder[i] > root) break
    }
    // 判断右子树中的元素是否都大于 root，此处用到 every (数组 API，数组的每个元素都返回 true 则整体返回 true)
    let result = postorder.slice(i, len - 1).every(x => x > root);
    if (result) {
        // 对左右子树进行递归调用,左右子树通过 i 进行分割
        return verifyPostorder(postorder.slice(0, i)) && verifyPostorder(postorder.slice(i, len - 1))
    } else {
        return false
    }
};