剑指 Offer 33. 二叉搜索树的后序遍历序列(中等)

发布时间 2023-08-21 20:41:28作者: 孜孜不倦fly

题目:

结合以下图理解该方法

class Solution {      //本题要点:二叉搜索树性质:根节点一定大于所有左子树,一定小于所有右子树 
public:
    bool traversal(vector<int>& postorder, int l, int r){      //l和r分别为当前树的左右边界
        if(l>=r) return true;
        int i=l, j=0;      //i用于比较大小并且确定左右子树边界
        while(postorder[i]<postorder[r]) i++;      //现在遍历左子树
        j=i;      //j用于保存左右子树的边界
        while(postorder[i]>postorder[r]) i++;      //现在遍历右子树
        return i==r&&traversal(postorder, l, j-1)&&traversal(postorder, j, r-1);      //i最终会指向右边界,左右递归均需要为真
    }
    bool verifyPostorder(vector<int>& postorder) {
        return traversal(postorder, 0, postorder.size()-1);
    }
};

作者:疯子
链接:https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solutions/1058657/2chong-jie-fa-qing-xi-luo-ji-miao-dong-o-23nq/
来源:力扣(LeetCode)