[数据结构与算法]验证二叉搜索树

说明

该题目来自LeetCode98，是比较经典的的二叉树遍历问题。记录一下该题目的多种解法。
题目描述
判断一个二叉树是不是二叉搜索树，二叉搜索树的特征如下：

• 结点的左子树只包含小于当前结点的数。
• 结点的右子树只包含大于当前结点的数。
• 左子树和右子树本身也是二叉搜索树。

二叉树的结点定义为：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

解法1 递归

递归的思想是：要保证整个树是二叉搜索树，则每个子树也是二叉搜索树。

class Solution {
public:
    bool compare(TreeNode* root,long lower,long upper)
    {
        if(root==nullptr) return true;  //空树满足条件

        if(root->val>=upper || root->val<=lower)
        {
            return false;
        } 
        //左子树和右子树都应该是二叉搜索树
        return compare(root->left,lower,root->val) && compare(root->right,root->val,upper);
    } 

    bool isValidBST(TreeNode* root) {
        return compare(root,LONG_MIN,LONG_MAX);
    }
};

其中，

return compare(root->left,lower,root->val) && compare(root->right,root->val,upper);

compare(root->left,lower,root->val)

表示判断左子树和根节点的大小，判断左子树时只需要更新上边界 $upper$。

compare(root->right,root->val,upper);

表示判断右子树和根节点的大小，判断右子树时只需要更新下边界 $lower$。

解法2 中序遍历

由BST的性质可以知道，BST中序遍历得到的一定是一个升序序列。所以，如果遍历结果不是升序的，则就说明这不是一个BST，否则说明这是一个BST。为此，我们需要用一个变量 $pre$ 来记录前一访问过的值，以便于和现在访问的值进行比较。

1、中序遍历 — 递归写法

递归写法1-无返回值递归

//1、中序遍历-递归写法1
class Solution {
public:
    long pre=LONG_MIN;
    void inOrder(TreeNode* root,bool& isSearchTree)
    {
        if(root==nullptr) return;
        inOrder(root->left,isSearchTree);
        if(root->val<=pre)  
        {
            isSearchTree=false;
            return;
        }
        pre=root->val;
        inOrder(root->right,isSearchTree);
    }

    bool isValidBST(TreeNode* root) {
        bool isSearchTree=true;
        inOrder(root,isSearchTree);
        return isSearchTree;
    }
};

递归写法2-有返回值非原地递归

//1、中序遍历-递归写法2
class Solution {
public:
    long pre=LONG_MIN;
    bool inOrder(TreeNode* root)
    {
        if(root==nullptr) return true;

        bool l=inOrder(root->left);
        if(root->val<=pre)
        {
            return false;
        }
        pre=root->val;  //修正
        bool r=inOrder(root->right);
        return l&&r;
    }
    bool isValidBST(TreeNode* root) {
        return inOrder(root);
    }
};

递归写法3-有返回值原地递归

从上面可以看到，直接可以使用原函数递归。

//1、中序遍历-递归写法3
class Solution {
public:
    long pre=LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root==nullptr) return true;
        bool l=isValidBST(root->left);
        if(root->val<=pre)
        {
            return false;
        }
        pre=root->val;  //修正
        bool r=isValidBST(root->right);
        return l&&r;
    }
};

2、中序遍历-非递归写法

可以使用栈来模拟中序遍历的过程。

//2、中序遍历-非递归写法
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        long pre=LONG_MIN;
        while(!stk.empty() || root!=nullptr)
        {
            while(root!=nullptr)
            {
                //左子树入栈
                stk.push(root);
                root=root->left;
            }
            root=stk.top();  //访问元素
            stk.pop();
            if(root->val<=pre)
            {
                return false;
            }
            pre=root->val;
            root=root->right;
        }
        return true;
    }
};

其中，非递归中序遍历的一般步骤为：

//非递归中序遍历的一般步骤
stack<TreeNode*> stk;
while(!stk.empty() || root!=nullptr)
{
	while(root!=nullptr)
	{
		stk.push(root);
		root=root->left;
	}
	root=stk.top();  
	stk.pop();
	
	//访问元素
	
	root=root->right;
}