剑指 Offer 33. 二叉搜索树的后序遍历序列
![【leetcode 二叉树 C++】【剑指 Offer】 33. 二叉搜索树的后序遍历序列 【leetcode 二叉树 C++】【剑指 Offer】 33. 二叉搜索树的后序遍历序列](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPTIwMjEwMTI4MjA0OTIzNTczLnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMjB3WHpNM05EVTBPRFV5LHNpemVfMTYsY29sb3JfRkZGRkZGLHRfNzA=)
class Solution {
public:
bool buildTree(vector<int> &postorder, vector<int> &inorder, int postL, int postR, int inL, int inR) {
if(postR == postL && inR == inL) return true;
if(postR - postL != inR - inL) return false;
int cnt = 0;
while(inL + cnt < inR && inorder[inL + cnt] != postorder[postR-1]) cnt++;
if(inL + cnt >= inR) return false;
bool left_flag = buildTree(postorder, inorder, postL, postL+cnt, inL, inL+cnt);
bool right_flag = buildTree(postorder, inorder, postL+cnt, postR-1, inL+cnt+1, inR);
return left_flag && right_flag;
}
bool verifyPostorder(vector<int>& postorder) {
vector<int> inorder(postorder.begin(), postorder.end());
sort(inorder.begin(), inorder.end()); // 对后序遍历结果排序可以得到中序遍历
return buildTree(postorder, inorder, 0, postorder.size(), 0, inorder.size()); // 根据中后序还原BST看是否出错
}
};