首页 > 代码库 > 23、剑指offer--二叉搜索树的后序遍历序列

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

题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 
解题思路:本题中的树为二叉搜索树,满足左<根<右
1)求出数组最后一个元素,为根节点
2)遍历,将所有连续小于sequence[n-1]的存入vector left中
3)将连续大于的存入vector right中  如果存在小于的,则直接返回false,无法构造二叉搜索树
4)然后对left进行递归处理,如果right为空则直接返回left_val
5)对right做递归处理,如果left为空,则直接返回right_val
6)否则返回(left_val && right_val)
 
注意点:本题中如果要遍历的数组的长度为1了,直接返回true,否则,递归永远返回false
 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     bool VerifySquenceOfBST(vector<int> sequence) {
 7 
 8         //根节点为数组最后一个元素
 9         int n = sequence.size();
10         if(n == 0)
11             return false;
12         if(n == 1)//没有此种情况,不行
13             return true;
14         int root = sequence[n-1];
15         vector<int> left;//存储左子树
16         vector<int> right;//存储右子树
17         //搜索二叉树,左子树均小于根,右子树均大于根
18         int i=0;
19         for(;i<n-1;i++)
20         {
21             if(sequence[i] > root)
22             {
23                 break;
24             }
25             left.push_back(sequence[i]);
26         }
27         //搜索二叉树,右子树均大于根
28         for(int j = i;j<n-1;j++)
29         {
30             if(sequence[j] < root)
31                 return false;
32             right.push_back(sequence[j]);
33         }
34 
35         //遍历左子树
36         bool left_val = true;
37         left_val = VerifySquenceOfBST(left);
38 
39         if(right.size()==0) //需要判断右子树是否为空,若只有左子树,返回
40             return left_val;
41         //遍历右子树
42         bool right_val = true;
43         right_val = VerifySquenceOfBST(right);
44 
45         if(left.size()==0)
46             return right_val;
47 
48         return (left_val && right_val);
49     }
50 };
51 int main()
52 {
53     vector<int> a;
54     a.push_back(5);
55     a.push_back(4);
56     a.push_back(3);
57     a.push_back(2);
58     a.push_back(1);
59 
60     Solution s;
61     bool r = s.VerifySquenceOfBST(a);
62     if(r)
63     {
64         cout<<"true"<<endl;
65     }
66     else
67     {
68         cout<<"false"<<endl;
69     }
70     return 0;
71 }

技术分享

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