附上原題：
一棵二叉樹如果屬于二叉搜索樹，必須滿足三個條件：
- 左子樹的所有節(jié)點都小于根節(jié)點
- 右子樹的所有節(jié)點都大于根節(jié)點
- 左子樹跟右子樹同時也是二叉搜索樹
我們看到第三條定義本身也是遞歸的碱妆。那根據(jù)該定義辛馆，如何來檢驗一棵二叉樹到底是不是二叉搜索樹？
首先百宇，如果左子樹跟右子樹其中有一棵不是二叉搜索樹的情況下考廉，則該二叉樹必定不屬于二叉搜索樹。那如何判定左子樹跟右子樹是不是二叉搜索樹呢携御？好像我們又回到了原來的問題昌粤。看一種比較特殊的情況啄刹，假如說二叉樹只有一個節(jié)點涮坐，即沒有左子樹也沒有右子樹，那么它必定屬于二叉搜索樹誓军。如果左子樹不存在袱讹，右子樹存在的情況下呢？此時左子樹就不需要再考慮是不是二叉搜索樹了昵时。反之右子樹不存在的情況下也一樣捷雕。
因此，對于這個問題壹甥，我們可以先考慮一棵二叉樹的葉子節(jié)點救巷。比如說有這樣一棵二叉樹：
左子樹跟右子樹都屬于葉子節(jié)點，必定是二叉搜索樹句柠。在符合第三條定義的情況下浦译，再來看前面兩條。根節(jié)點大于左子樹的所有節(jié)點溯职，難道要用根節(jié)點與左子樹的每個節(jié)點去比較精盅？我們換個角度想，是不是只要根節(jié)點大于左子樹最大的節(jié)點就可以了谜酒？因為在確定左子樹屬于二叉搜索樹的情況下叹俏，只要沿著左子樹的根節(jié)點出發(fā)一直向右即可找到最大的節(jié)點。同樣甚带，對于第二個定義她肯，根節(jié)點只需小于右子樹最小的節(jié)點即可。
我們運用了一種“分而治之”的思想鹰贵，先考慮最基本的情況晴氨，即葉子節(jié)點，再得到左子樹和右子樹同時為二叉搜索樹的前提下碉输，用當前樹的根節(jié)點去比較左子樹的最大值和右子樹的最小值籽前。然后算法不斷得往上回溯，最終得出整棵樹是不是二叉搜索樹。
根據(jù)以上分析枝哄，我們設計出如下算法：
- 如果當前節(jié)點即不存在左子樹也不存在右子樹肄梨，直接返回true。
- 如果當前節(jié)點存在左子樹挠锥，則驗證左子樹是否為二叉搜索樹众羡，若是，并且根節(jié)點大于左子樹的最大值蓖租，則左子樹驗證通過粱侣。若左子樹不存在，同樣驗證通過蓖宦。
- 如果當前節(jié)點存在右子樹齐婴，則驗證右子樹是否為二叉搜索樹，若是稠茂，并且根節(jié)點小于右子樹的最小值柠偶，右子樹驗證通過。若右子樹不存在睬关，同樣驗證通過诱担。
- 若左子樹跟右子樹同時驗證通過，返回true共螺；否則该肴，返回false情竹。
看代碼：
class Solution {
public:
bool isValidBST(TreeNode* root) {
bool isValidLeft = true;
bool isValidRight = true;
if (root) {
int val = root->val;
if (root->left) {
//驗證左子樹是否為二叉搜索樹藐不，并且根節(jié)點大于左子樹的最小值
isValidLeft = isValidBST(root->left) && (val > fetchMaxNodeVal(root->left));
}
if (root->right) {
isValidRight = isValidBST(root->right) && (val < fetchMinNodeVal(root->right));
}
if (!root->left && !root->right) {
return true;
}
}
return isValidLeft && isValidRight;
}
private:
//獲取二叉樹的最大值
int fetchMaxNodeVal(TreeNode *node) {
while (node->right) {
node = node->right;
}
return node->val;
}
int fetchMinNodeVal(TreeNode *node) {
while (node->left) {
node = node->left;
}
return node->val;
}
};
