給定一個(gè)二叉樹(shù)，判斷它是否是合法的二叉查找樹(shù)(BST)
一棵BST定義為：
節(jié)點(diǎn)的左子樹(shù)中的值要嚴(yán)格小于該節(jié)點(diǎn)的值介汹。
節(jié)點(diǎn)的右子樹(shù)中的值要嚴(yán)格大于該節(jié)點(diǎn)的值却嗡。
左右子樹(shù)也必須是二叉查找樹(shù)。
一個(gè)節(jié)點(diǎn)的樹(shù)也是二叉查找樹(shù).
思路:中根序遍歷這棵樹(shù)嘹承，保存所有節(jié)點(diǎn)值到vector中窗价，此時(shí)容器內(nèi)的值應(yīng)當(dāng)是升序的
bool isValidBST(TreeNode * root) {
// write your code here
if( !root )
{
return true;
}
std::vector<int> vc;
NLR(root,vc);
int len = vc.size();
for(int i = 0; i < len - 1; ++i)
{
if(vc[i + 1] <= vc[i])
{
return false;
}
}
return true;
}
void NLR(TreeNode * root,std::vector<int> &vc)
{
if( root)
{
NLR(root->left,vc);
vc.push_back(root->val);
NLR(root->right,vc);
}
}
