[剑指offer]二叉搜索树的后序遍历数列

[剑指offer]二叉搜索树的后序遍历数列

剑指offer-二叉搜索树的后序遍历序列

题目描述

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

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

5 / \ 2 6 / \ 1

示例 1： 输入: [1,6,3,2,5] 输出: false

示例 2： 输入: [1,3,2,6,5] 输出: true

提示： 数组长度 <= 1000

解题思路

二叉搜索树特点：若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。后序遍历序列的最后一个值为二叉树的根节点，前面分为两部分，前半部分都小于根节点的值，后半部分都大于根节点的值。假设后序遍历序列长度为len，最后一个值为root，找出序列中第一个大于root的值的位置i，那么[0，i)为它的左子树，[i，len)为它的右子树。

实现代码

class Solution { public: bool verifyPostorder(vector<int>& postorder) { int len = postorder.size(); if(len==0) return true; int root = postorder[len-1];//根节点的值 vector<int> left; vector<int> right; int temp=0; for(int i=0;i<len-1;i++){//得到左子树序列 temp=i;//保存第一个大于root值的位置 if(postorder[i]<root) left.push_back(postorder[i]);//左子树 else//找到了第一个大于root的值，temp保存了它的位置 break; } if(temp==len-2)//说明左边的值都小于root，没有右子树 temp=temp+1; for(int i=temp;i<len-1;i++){//得到右子树序列 if(postorder[i]<root)//如果[temp，len-1)中有小于root值得，返回flase return false; right.push_back(postorder[i]);//右子树 } if(verifyPostorder(left)&verifyPostorder(right))//递归，判断左子树和右子树是否都符合二叉搜索树条件 return true; return false; } };