题面
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
示例
示例 1:
1 2
| 输入: [1,6,3,2,5] 输出: false
|
示例 2:
1 2
| 输入: [1,3,2,6,5] 输出: true
|
限制
思路
按照后续遍历的实现最后一个元素是根节点, 比根节点的小的说明是在左子树,比根节点大的说明在右子树。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { bool dfs(vector<int>& postorder, int start, int end){ if(start >= end) return true;
int p = start; int rootval = postorder[end]; while(postorder[p] < rootval){ ++p; } int leftEnd = p-1;
while(postorder[p] > rootval){ ++p; }
return p==end && dfs(postorder, start, leftEnd) && dfs(postorder, leftEnd+1, end-1); } public: bool verifyPostorder(vector<int>& postorder) { return dfs(postorder, 0, postorder.size()-1); } };
|