力扣 驗證二叉搜尋樹

題目描述

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜尋樹。

有效 二叉搜尋樹定義如下：

節點的左子樹隻包含 小于 目前節點的數。

節點的右子樹隻包含 大于 目前節點的數。

所有左子樹和右子樹自身必須也是二叉搜尋樹。

示例 1：

輸入：root = [2,1,3]

輸出：true

示例 2：

輸入：root = [5,1,4,null,null,3,6]

輸出：false

解釋：根節點的值是 5 ，但是右子節點的值是 4 。

思路分析

此題目需要保證任何節點的左子樹的最右邊的節點小于該節點，任何節點的右子樹的最左邊的節點大于該節點。

通過分析我們發現此題實際上是要求出中序周遊二叉樹的序列，然後判斷該序列是否為遞增序列即可。

代碼如下：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int>res;
        TreeNode* p=root;
        while(p!=nullptr||!s.empty()){
            while(p!=nullptr){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                res.push_back(p->val);
                s.pop();
                p=p->right;
            }
        }
        for(int i=0;i<res.size()-1;i++){
            if(res[i]>=res[i+1])return false;
        }
        return true;
    }
};