题解 | #判断是不是二叉搜索树#

题目主要信息：

• 判断给定的一棵二叉树是否是二叉搜索树
• 二叉搜索树每个左子树元素小于根节点，每个右子树元素大于根节点，中序遍历为递增序

举一反三：

学习完本题的思路你可以解决如下题目：

BM30. 二叉搜索树与双向链表

BM37. 二叉搜索树的最近公共祖先

方法一：递归（推荐使用）

知识点1：二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

知识点2：二叉搜索树

二叉搜索树是一种特殊的二叉树，它的每个节点值大于它的左子节点，且大于全部左子树的节点值，小于它右子节点，且小于全部右子树的节点值。因此二叉搜索树一定程度上算是一种排序结构。

思路：

二叉搜索树的特性就是中序遍历是递增序。既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断。*只不过在过程中我们要求反退出。比如一个链表1->2->3->4，只要for循环遍历如果中间有不是递增的直接返回false即可。

if(root.val < pre)
    return false;

具体做法：

• step 1：首先递归到最左，初始化maxLeft与pre。
• step 2：然后往后遍历整棵树，依次连接pre与当前节点，并更新pre。
• step 3：左子树如果不是二叉搜索树返回false。
• step 4：判断当前节点是不是小于前置节点，更新前置节点。
• step 5：最后由右子树的后面节点决定。

Java实现代码：

import java.util.*;
public class Solution {
    int pre = Integer.MIN_VALUE;
    //中序遍历
    public boolean isValidBST (TreeNode root) { 
        if (root == null)
            return true;
        //先进入左子树
        if(!isValidBST(root.left)) 
            return false;
        if(root.val < pre)
            return false;
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right); 
    }
}

C++实现代码：

class Solution {
public:
    long pre = INT_MIN;
    //中序遍历
    bool isValidBST(TreeNode* root) {
        if(root == NULL)
            return true;
        //先进入左子树
        if(!isValidBST(root->left)) 
            return false;
        if(root->val <= pre)
            return false;
        //更新最值
        pre = root->val;  
        //再进入右子树
        if(!isValidBST(root->right))  
            return false;
        return true;
    }
};

Python实现代码

import sys
class Solution:
    pre = -sys.maxsize - 1
    def isValidBST(self , root: TreeNode) -> bool:
        if not root:
            return True
        # 先进入左子树
        if not self.isValidBST(root.left): 
            return False
        if(root.val <= self.pre):
            return False
        # 更新最值
        self.pre = root.val  
        # 再进入右子树
        if not self.isValidBST(root.right):  
            return False
        return True

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树的节点数，最坏遍历整个二叉树所有节点
• 空间复杂度：$O(n)O(n)$，最坏情况二叉树退化为链表，递归栈深度为$nn$

方法二：非递归（扩展思路）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

我们也可以利用栈来代替递归。如果一棵二叉树，对于每个根节点都优先访问左子树，那结果是什么？从根节点开始不断往左，第一个被访问的肯定是最左边的节点， 然后访问该节点的右子树，最后向上回到父问题。因为每次访问最左的元素不止对一整棵二叉树成立，而是对所有子问题都成立，因此循环的时候自然最开始都是遍历到最左：

//直到没有左节点
while(head != null){   
    s.push(head);
    head = head.left;
}

然后访问，然后再进入右子树，我们可以用栈来实现回归父问题。

具体做法：

• step 1：优先判断树是否为空，空树不遍历。
• step 2：准备一个数组记录中序遍历的结果。
• step 3：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
• step 4：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
• step 5：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。
• step 6：遍历数组，依次比较相邻两个元素是否为递增序。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public boolean isValidBST(TreeNode root){
        //设置栈用于遍历
        Stack<TreeNode> s = new Stack<TreeNode>(); 
        TreeNode head = root;
        //记录中序遍历的数组
        ArrayList<Integer> sort = new ArrayList<Integer>(); 
        while(head != null || !s.isEmpty()){
            //直到没有左节点
            while(head != null){   
                s.push(head);
                head = head.left;
            }
            head = s.pop();
            //访问节点
            sort.add(head.val); 
            //进入右边
            head = head.right; 
        }
        //遍历中序结果
        for(int i = 1; i < sort.size(); i++){ 
            //一旦有降序，则不是搜索树
            if(sort.get(i - 1) > sort.get(i)) 
                return false;
        }
        return true;
    }
}

C++实现代码：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        //设置栈用于遍历
        stack<TreeNode*> s; 
        TreeNode* head = root;
        vector<int> sort; //记录中序遍历的数组
        while(head != NULL || !s.empty()){
            //直到没有左节点
            while(head != NULL){   
                s.push(head);
                head = head->left;
            }
            head = s.top();
            s.pop();
            //访问节点
            sort.push_back(head->val);
            head = head->right;
        }
        //遍历中序结果
        for(int i = 1; i < sort.size(); i++){ 
            //一旦有降序，则不是搜索树
            if(sort[i - 1] > sort[i]) 
                return false;
        }
        return true;
    }
};

Python实现代码

class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        # 设置栈用于遍历 和 记录中序遍历的数组
        s ,sort = [], [] 
        head = root
        while head or s:
            # 直到没有左节点
            while head:   
                s.append(head)
                head = head.left
            head = s[-1]
            s.pop()
            # 访问节点
            sort.append(head.val) 
            head = head.right
        # 遍历中序结果
        for i in range(1, len(sort)):  
            # 一旦有降序，则不是搜索树
            if sort[i - 1] > sort[i]: 
                return False
        return True

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为二叉树的节点数，遍历整个二叉树后又遍历数组
• 空间复杂度：$O(n)O(n)$，辅助栈及辅助数组的空间最坏为$O(n)O(n)$