1.题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

2.解法分析

对树进行先序遍历，如果先序遍历的过程中始终有前一个元素比后一个元素小，那么就是一棵有效的BST，反之则不是

/**

* Definition for binary tree

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

bool isValidBST(TreeNode *root) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(!root)return true;

vector
           
             v;
           

int cur;

int prev;

bool firstRound=true;

TreeNode *curT=root;

while(curT||!v.empty())

{

while(curT)

{

v.push_back(curT);

curT=curT->left;

}

if(!v.empty())

{

curT=v.back();v.pop_back();

if(firstRound){cur=curT->val;prev=cur;firstRound=false;}

else

{

cur=curT->val;

if(cur<=prev)return false;

prev=cur;

}

curT=curT->right;

}

}

return true;

}

};