附上原題：
一棵二叉樹如果屬于二叉搜索樹，必須滿足三個(gè)條件：
- 左子樹的所有節(jié)點(diǎn)都小于根節(jié)點(diǎn)
- 右子樹的所有節(jié)點(diǎn)都大于根節(jié)點(diǎn)
- 左子樹跟右子樹同時(shí)也是二叉搜索樹
我們看到第三條定義本身也是遞歸的。那根據(jù)該定義，如何來(lái)檢驗(yàn)一棵二叉樹到底是不是二叉搜索樹？
首先，如果左子樹跟右子樹其中有一棵不是二叉搜索樹的情況下，則該二叉樹必定不屬于二叉搜索樹。那如何判定左子樹跟右子樹是不是二叉搜索樹呢？好像我們又回到了原來(lái)的問題?？匆环N比較特殊的情況，假如說二叉樹只有一個(gè)節(jié)點(diǎn)，即沒有左子樹也沒有右子樹，那么它必定屬于二叉搜索樹。如果左子樹不存在，右子樹存在的情況下呢？此時(shí)左子樹就不需要再考慮是不是二叉搜索樹了。反之右子樹不存在的情況下也一樣。
因此，對(duì)于這個(gè)問題，我們可以先考慮一棵二叉樹的葉子節(jié)點(diǎn)。比如說有這樣一棵二叉樹：
左子樹跟右子樹都屬于葉子節(jié)點(diǎn)，必定是二叉搜索樹。在符合第三條定義的情況下，再來(lái)看前面兩條。根節(jié)點(diǎn)大于左子樹的所有節(jié)點(diǎn)，難道要用根節(jié)點(diǎn)與左子樹的每個(gè)節(jié)點(diǎn)去比較？我們換個(gè)角度想，是不是只要根節(jié)點(diǎn)大于左子樹最大的節(jié)點(diǎn)就可以了？因?yàn)樵诖_定左子樹屬于二叉搜索樹的情況下，只要沿著左子樹的根節(jié)點(diǎn)出發(fā)一直向右即可找到最大的節(jié)點(diǎn)。同樣，對(duì)于第二個(gè)定義，根節(jié)點(diǎn)只需小于右子樹最小的節(jié)點(diǎn)即可。
我們運(yùn)用了一種“分而治之”的思想，先考慮最基本的情況，即葉子節(jié)點(diǎn)，再得到左子樹和右子樹同時(shí)為二叉搜索樹的前提下，用當(dāng)前樹的根節(jié)點(diǎn)去比較左子樹的最大值和右子樹的最小值。然后算法不斷得往上回溯，最終得出整棵樹是不是二叉搜索樹。
根據(jù)以上分析，我們?cè)O(shè)計(jì)出如下算法：
- 如果當(dāng)前節(jié)點(diǎn)即不存在左子樹也不存在右子樹，直接返回true。
- 如果當(dāng)前節(jié)點(diǎn)存在左子樹，則驗(yàn)證左子樹是否為二叉搜索樹，若是，并且根節(jié)點(diǎn)大于左子樹的最大值，則左子樹驗(yàn)證通過。若左子樹不存在，同樣驗(yàn)證通過。
- 如果當(dāng)前節(jié)點(diǎn)存在右子樹，則驗(yàn)證右子樹是否為二叉搜索樹，若是，并且根節(jié)點(diǎn)小于右子樹的最小值，右子樹驗(yàn)證通過。若右子樹不存在，同樣驗(yàn)證通過。
- 若左子樹跟右子樹同時(shí)驗(yàn)證通過，返回true；否則，返回false。
看代碼：
class Solution {
public:
bool isValidBST(TreeNode* root) {
bool isValidLeft = true;
bool isValidRight = true;
if (root) {
int val = root->val;
if (root->left) {
//驗(yàn)證左子樹是否為二叉搜索樹，并且根節(jié)點(diǎn)大于左子樹的最小值
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;
}
};
