题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
二叉搜索树的特点就是永远是左子树<根<右子树。看到二叉树，首先想到的是递归，选择了递归，那么我们只要想好判断根，左子树，右子树的条件就可以，后序遍历，最后一个必然是根，所以当遍历序列为空时为假无疑问，但遍历序列长度为1和2时必然也可以画出相应的二叉搜索树，所以可直接判定为真，当序列长度大于等于3时，则分为3种情况：二叉树只有左子树[1,2,3,4,5],二叉树只有右子树[2,3,4,5,1],既有左子树又有右子树[1,2,4,5,3]，分类判定。进行变量命名时还是要有明显的区分，这道题困扰了我三天，到最后结果就是l错写成了r。
代码
class Solution {
public:
bool VerifySquenceOfBST(vector
<int> sequence
) {
if (sequence
.empty())
{
return false;
}
else if (sequence
.size()==1 || sequence
.size()==2)
{
return true;
}
else
{
int root
= sequence
.back();
int index
= 0;
vector
<int> sequencel
,sequencer
;
if (sequence
[0] > root
)
{
for (int ir
= 0; ir
<sequence
.size()-1; ir
++)
{
sequencer
.push_back(sequence
[ir
]);
if (sequence
[ir
]<root
)
{
return false;
}
}
return VerifySquenceOfBST(sequencer
);
}
else if (sequence
[sequence
.size()-2] < root
)
{
for (int il
= 0; il
<sequence
.size()-1; il
++)
{
sequencel
.push_back(sequence
[il
]);
if (sequence
[il
] > root
)
{
return false;
}
}
return VerifySquenceOfBST(sequencel
);
}
else
{
for (int i
= 0; i
< sequence
.size();i
++)
{
if (sequence
[i
] < root
&& sequence
[i
+1] >root
)
{
index
= i
;
break;
}
}
for (int j
= 0; j
<= index
;j
++)
{
sequencel
.push_back(sequence
[j
]);
if (sequence
[j
]> root
)
{
return false;
}
}
for (int k
= index
+1; k
<sequence
.size()-1; k
++)
{
sequencer
.push_back(sequence
[k
]);
if (sequence
[k
] < root
)
{
return false;
}
}
return VerifySquenceOfBST(sequencel
) && VerifySquenceOfBST(sequencer
);
}
}
}
};
