題目

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特征：

節點的左子樹只包含小于當前節點的數。
節點的右子樹只包含大于當前節點的數。
所有左子樹和右子樹自身必須也是二叉搜索樹。

1、利用BST性質：中序遍歷結果遞增

由平衡二叉樹的性質可知，若是用中序遍歷方法，得到的結果會是遞增的。
初次外，如果root的結點為空或者只有1個結點的時候，我們認為它也是一棵二叉搜索樹。
以這樣的思路寫出的遞歸代碼：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void traversal(TreeNode* cur , vector<int>& vec){if(cur == NULL) return;traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec);}bool isValidBST(TreeNode* root) {vector<int> result;traversal(root,result);for(int i =1;i<result.size();i++){if(result[i-1]>=result[i]) return false;//cout<<result[i]<<endl;}return true;}
};

2、不使用數組，進行優化

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* pre =NULL;        //用來記錄前一個結點bool isValidBST(TreeNode* root) {if(root ==NULL) return true;//檢查左子樹是否為二叉搜索樹bool left =isValidBST(root->left);//檢查此中間結點與上一個中間結點是否是單調遞增的關系if(pre != NULL && pre->val >= root->val) return false;pre = root;  //更新結點//檢查右子樹是否為二叉搜索樹bool right = isValidBST(root->right);//左子樹和右子樹自身必須也是二叉搜索樹return left && right;}
};

3、回顧迭代法求解

對迭代法中序遍歷稍加改動：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL;while(cur!=NULL || !st.empty()){if(cur !=NULL){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();if(pre != NULL && cur->val <= pre->val) return false;pre = cur;cur = cur->right;}}return true;}
};