【leetcode】98. 验证二叉搜索树

问题描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

提示：

• 树中节点数目范围在[1, $10^4$] 内
• $-2^{31}$ <= Node.val <= $2^{31}$ - 1

注意节点值的取值范围[$-2^{31}$ , $2^{31}$ - 1]，二叉搜索树的定义节点值不能等于，处理时需要注意初始值的设置。这里取巧采用LONG_MIN和LONG_MAX避免。

解决方案

对于树相关的题目，使用递归一般是比较简单的解决方案，但借助栈有时候可以达到更优的性能。

解决方案1:后序遍历

核心思想：先检查左右子树是否有效，然后将当前节点跟左子树的最大节点和右子树的最小节点比较

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        auto result = validBST(root);
        return get<0>(result);
    }
    //返回值为 是否有效，最小节点，最大节点
    tuple<bool,TreeNode*,TreeNode*> validBST(TreeNode* root) {
        if(root == nullptr){
            return make_tuple(true, nullptr, nullptr);
        }
        tuple<bool,TreeNode*,TreeNode*> left = validBST(root->left);
        if(!get<0>(left)){
            return make_tuple(false, nullptr, nullptr);
        }
        tuple<bool,TreeNode*,TreeNode*> right = validBST(root->right);
        if(!get<0>(right)){
            return make_tuple(false, nullptr, nullptr);
        }
        //将当前节点跟左子树的最大节点比较
        if(get<2>(left) && root->val <= get<2>(left)->val){
            return make_tuple(false, nullptr, nullptr);
        }
        //将当前节点跟右子树的最小节点比较
        if(get<1>(right) && root->val >= get<1>(right)->val){
            return make_tuple(false, nullptr, nullptr);
        }
        //返回以该节点为根的子树的最小最大节点
        return make_tuple(true, (get<1>(left) ? get<1>(left) : root), 
        (get<2>(right) ? get<2>(right) : root));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解决方案2: 自顶向下递归

核心思想：当前节点node的取值范围在(left,right),那么左子树的取值范围在(left, root->val),那么右子树的取值范围在(node->val, right)，不断切分子树的取值范围，直到叶子节点。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validBST(root, LONG_MIN, LONG_MAX);
    }
    bool validBST(TreeNode* root, long left, long right) {
        if(root == nullptr){
            return true;
        }
        if(root->val <= left || root->val >= right){
            return false;
        }
        return validBST(root->left, left, root->val) &&
         validBST(root->right, root->val, right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解决方案3: 中序遍历（递归版）

核心思想：二叉搜索树按照中序遍历正好是有序序列，所以可以采用中序遍历的方式，并检查当前节点是否大于前一节点值。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long pre = LONG_MIN;
        return validBST(root, pre);
    }
    bool validBST(TreeNode* root, long& pre) {
        if(root == nullptr){
            return true;
        }
        if(!validBST(root->left, pre)){
            return false;
        }
        if(root->val <= pre){
            return false;
        }
        pre = root->val;
        return validBST(root->right, pre);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解决方案4: 中序遍历（非递归破坏版）

核心思想：使用栈来模拟递归，在此过程中会改变树结构，改变树结构的原因是避免重复入栈。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        stack<TreeNode*> st;
        st.push(root);
        TreeNode* pre = nullptr;
        while(!st.empty()){
            TreeNode* top = st.top();
            if(top->left){
                st.push(top->left);
                //由于是逐节点处理，必须在该节点的左右子树入栈后，将其左右子树置空，避免下次弹出后又会重新入栈
                top->left = nullptr;
                continue;
            }
            st.pop();
            if(pre && top->val <= pre->val){
                return false;
            }
            pre = top;
            if(top->right){
                st.push(top->right);
                top->right = nullptr;
            }
        }
        return true;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

解决方案5: 中序遍历（非递归不破坏版）

核心思想：使用栈来模拟递归，在此过程中保证树结构不变，在处理过程中，会一直沿着做节点做入栈操作，当弹出该节点时，将只考虑右节点。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        stack<TreeNode*> st;
        TreeNode* pre = nullptr;
        while(!st.empty() || root != nullptr){
            //一直将左子树入栈
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            if(pre && root->val <= pre->val){
                return false;
            }
            pre = root;
            //必须要重置root为右节点
            root = root->right;
        }
        return true;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27