1. 題目

輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回 true，否則返回 false。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。

參考以下這顆二叉搜索樹：5/ \2 6/ \1 3 示例 1： 輸入: [1,6,3,2,5] 輸出: false示例 2： 輸入: [1,3,2,6,5] 輸出: true提示： 數(shù)組長度 <= 1000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 二叉搜索樹，左子樹<root, 右子樹>root
• 后序：左右根，根在最后

class Solution { public:bool verifyPostorder(vector<int>& postorder) {if(postorder.size() <= 2)return true;return check(postorder,0,postorder.size()-1);}bool check(vector<int>& order, int L, int R) {if(L >= R)//區(qū)間只有1個或者沒有元素了return true;int root = order[R];//根int i = L, j = R-1;//左子樹的區(qū)間指針i，右子樹jwhile(i < R && order[i] < root)i++;while(j >= L && order[j] > root)j--;if(i-j != 1)//最終j應(yīng)該緊貼i的左側(cè)return false;return check(order,L,i-1) && check(order,j+1,R-1);//遞歸查找2側(cè)子樹} };

總結(jié)

以上是生活随笔為你收集整理的剑指Offer - 面试题33. 二叉搜索树的后序遍历序列（递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。