【LeetCode】98. Validate Binary Search Tree 解法，中序遍历，搜索二叉树合法性

忘是亡心i 2022-07-28 10:54 149阅读 0赞

98. Validate Binary Search Tree

Total Accepted: 90083 Total Submissions: 430775 Difficulty: Medium

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

*  The left subtree of a node contains only nodes with keys less than the node's key.
 *  The right subtree of a node contains only nodes with keys greater than the node's key.
 *  Both the left and right subtrees must also be binary search trees.

confused what `"{1,#,2,3}"` means? [> read more on how binary tree is serialized on OJ.][read more on how binary tree is serialized on OJ.]

【分析】

根据二叉搜索树（BST）的性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别构成二叉搜索树，满足同样性质。判断一个给定的二叉树是否为搜索二叉树，最直观的方法就是根据其性质来判断：如二叉树\[10,5,15,\#,\#,6,20\]，如下图所示二叉树，对其进行判断的过程为：

1、对于根节点10，其左子树节点5是否小于10，其右子树包含节点15,6,20，需要逐一判别是否大于10；

2、如果1满足则进行下一步，将节点5作为根节点，按照1中的方法判断其左子树中的所有节点是否均小于5，其右子树中的所有节点是否大于5；同时，将节点15作为根节点，按照1中的方法判断其左子树中的所有节点是否均小于15，其右子树中的所有节点是否大于15；

3、根据上述过程，很明显，这个判断过程可以用“**递归**”解决，但，针对每一个根节点，我们都需要将其值与其左右子树中的所有节点与之进行比较，时间复杂度为**O(n2)**.

![Center][]

进一步地分析，二叉搜索树还有一个非常重要的性质：它的**中序遍历**为递增序列，上图进行中序遍历（左，根，右）得：5,10,6,15,20，6的位置出现降序，因此该二叉树不是二叉搜索树。采用中序遍历的思路判断二叉搜索树的合法性更为简洁，一次遍历即可完成，事件复杂度仅为**O(n)**。

【解法】

“递归”法：

/**
     * 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) 
        {
            if(root==NULL)return true;
            else if(!checkleft(root->left,root->val)||!checkright(root->right,root->val)) return false;
            
            return isValidBST(root->left)&&isValidBST(root->right);//进入下一层，原根节点的左右子节点作为根节点
        }
        
        bool checkleft(TreeNode *root,int value)
        {
            if(root==NULL)return true;
            if(root->val>=value)return false;
            return checkleft(root->left,value)&&checkleft(root->right,value);//注意细节
        }
        bool checkright(TreeNode *root,int value)
        {
            if(root==NULL)return true;
            if(root->val<=value)return false;
            return checkright(root->right,value)&&checkright(root->left,value);//注意细节
        }
    };

“中序遍历”版解法

class Solution {
        
    private:
        vector<int> inorderList;//存储遍历结果
    public:
        bool isValidBST(TreeNode* root) 
        {
            if(root==NULL)return true;//根节点为空
            inorderTraversal(root);
            if(inorderList.size()==1)return true;//只有一个节点
            for(int i=1;i<inorderList.size();i++)//检验中序遍历结果是否为升序
            {
                if(inorderList[i]<=inorderList[i-1])return false;
            }
            return true;
        }
    
        void inorderTraversal(TreeNode *root)//中序遍历
        {
            if(root==NULL)return;
            
            inorderTraversal(root->left);
            inorderList.push_back(root->val);
            inorderTraversal(root->right);
            
        }
        
    };

[read more on how binary tree is serialized on OJ.]: https://leetcode.com/problems/validate-binary-search-tree/#
[Center]: /images/20220724/873c6e8e499248478352642c4f468904.png