leetcode98：验证二叉搜索树

题目链接

leetcode

题目描述

给一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

C++ 代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

// 二叉树结点的定义
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) {}
};

const int NULL_NODE = 0;

// 辅助函数：创建二叉树
TreeNode* createTree(const vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> queue;
    queue.push(root);
    int i = 1;
    while (!queue.empty() && i < nums.size()) {
        TreeNode* node = queue.front(); queue.pop();
        if (nums[i] != NULL_NODE) {
            node->left = new TreeNode(nums[i]);
            queue.push(node->left);
        }
        i ++;
        if (i < nums.size() && nums[i] != NULL_NODE) {
            node->right = new TreeNode(nums[i]);
            queue.push(node->right);
        }
        i ++;
    }

    return root;
}

// 辅助函数：层序遍历打印二叉树
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> queue;
    queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front(); queue.pop();
        cout << node->val << " ";
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
    cout << endl;
}

// 辅助函数：释放二叉树
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

/*
    深度优先遍历，递归实现

    对于每个结点，传递其允许的最小值和最大值范围。
        遍历它的左子树，判断左子树是否有效，判断左子树的最大值是否小于当前结点的值；
        遍历它的右子树，判断右子树是否有效，同时判断右子树的最小值是否大于当前结点的值。
    若条件均满足，则说明以当前结点为根的子树是一棵二叉搜索树，返回 true。 

    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，树中每个结点被遍历一次。
*/
class Solution_0 {
public:
    bool isValidBST(TreeNode* root) {
        int minVal, maxVal;
        return dfs(root, minVal, maxVal);
    }

    bool dfs(TreeNode* root, int &minVal, int &maxVal) {
        if (root == nullptr) return true;

        minVal = maxVal = root->val;
        if (root->left) {
            int tMinVal, tMaxVal;
            if (!dfs(root->left, tMinVal, tMaxVal)) return false;
            if (tMaxVal >= root->val) return false;
            minVal = min(minVal, tMinVal);
            maxVal = max(maxVal, tMaxVal);
        }
        if (root->right) {
            int tMinVal, tMaxVal;
            if (!dfs(root->right, tMinVal, tMaxVal)) return false;
            if (tMinVal <= root->val) return false;
            minVal = min(minVal, tMinVal);
            maxVal = max(maxVal, tMaxVal);
        }

        return true;
    }
};

// 思路同上
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, nullptr, nullptr);
    }

    bool dfs(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if (root == nullptr) return true;
        if (minNode && root->val <= minNode->val) return false;
        if (maxNode && root->val >= maxNode->val) return false;
        // 递归地检查左子树和右子树（左子树的最大值是当前结点，右子树的最小值是当前结点）
        return dfs(root->left, minNode, root)
            && dfs(root->right, root, maxNode);
    }
};

/*
    深度优先遍历，迭代实现

    深搜过程中维护信息
        res[0]: 是否满足 BST（0 表示不满足，1 表示满足）
        res[1]: 以该结点为根，其子树中的最小值
        res[2]: 以该结点为根，其子树中的最大值
*/
class Solution_2 {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        return dfs(root)[0];
    }

    vector<int> dfs(TreeNode* root) {
        vector<int> res = {1, root->val, root->val}; // 是否满足 BST，子树中的最小值，子树中的最大值
        if (root->left) {
            vector<int> t = dfs(root->left);
            if (!t[0] || t[2] >= root->val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }
        if (root->right) {
            vector<int> t = dfs(root->right);
            if (!t[0] || t[1] <= root->val) res[0] = 0;
            res[1] = min(res[1], t[1]);
            res[2] = max(res[2], t[2]);
        }

        return res;
    }
};

/*
    中序遍历，并检查当前结点是否比前一结点大，
    若不符合该条件，则说明不是二叉搜索树。

    时间复杂度：O(n)
        其中 n 为二叉树结点的个数，树中每个结点被遍历一次。
*/
// 递归实现
class Solution_3 {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        // 左子树
        if (!isValidBST(root->left)) return false;
        // 访问当前结点
        if (prev != nullptr && root->val <= prev->val) return false;
        prev = root;
        // 右子树
        return isValidBST(root->right);
    }
    
private:
    TreeNode* prev = nullptr;
};
// 迭代实现
class Solution_4 {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        stack<TreeNode*> stk;
        while (root || stk.size()) {
            // 遍历左子树
            while (root) {
                stk.push(root);
                root = root->left;
            }
            // 访问当前结点
            root = stk.top(); stk.pop();
            if (prev != nullptr && prev->val >= root->val) return false;
            prev = root;
            // 遍历右子树
            root = root->right;
        }

        return true;
    }

private:
    TreeNode* prev = nullptr;
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {2, 1, 3};

    // 创建二叉树
    TreeNode* root = createTree(nums);
    // 打印二叉树
    levelOrderTraversal(root);

    // 验证是否为二叉搜索树
    bool result = solution.isValidBST(root);
    // 打印结果
    cout << "Is BST: " << (result ? "true" : "false") << endl;

    // 释放内存
    deleteTree(root);

    return 0;
}

Golang 代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package main

import (
	"fmt"
	"math"
)

// 定义二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 创建二叉树
func createTree(values []int) *TreeNode {
	if len(values) == 0 {
		return nil
	}
	root := &TreeNode{Val: values[0]}
	queue := []*TreeNode{root}
	i := 1
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]

		if i < len(values) && values[i] != -1 {
			node.Left = &TreeNode{Val: values[i]}
			queue = append(queue, node.Left)
		}
		i++

		if i < len(values) && values[i] != -1 {
			node.Right = &TreeNode{Val: values[i]}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// 打印二叉树（层序遍历）
func printTree(root *TreeNode) string {
	if root == nil {
		return "[]"
	}
	result := []int{}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == nil {
			result = append(result, -1)
			continue
		}
		result = append(result, node.Val)
		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}
	// 去掉尾部的 -1
	for len(result) > 0 && result[len(result)-1] == -1 {
		result = result[:len(result)-1]
	}
	return fmt.Sprintf("%v", result)
}

/*
    基本思路：深度优先遍历
        对于每个节点，传递其允许的最小值和最大值范围。
            遍历它的左子树，判断左子树是否有效，判断左子树的最大值是否小于当前节点的值；
            遍历它的右子树，判断右子树是否有效，同时判断右子树的最小值是否大于当前节点的值。
        若条件均满足，则说明以当前节点为根的子树是一棵二叉搜索树，返回 true。 
    
    时间复杂度：O(n)
        其中 n 是二叉树的节点数量，需要访问每个节点一次。
    空间复杂度：O(logn)
        取决于递归调用栈的深度。
        在平均情况下，树的高度为 O(logn)，所以空间复杂度为 O(logn)；
        在最坏情况下，树退化为链表，空间复杂度为 O(n)。
        但平均情况下，空间复杂度接近 O(logn)。
*/
// 递归实现
func isValidBST(root *TreeNode) bool {
    return dfs(root, math.MinInt64, math.MaxInt64)
}

func dfs(root *TreeNode, min, max int) bool {
    if root == nil {
        return true
    }
    // 访问当前节点：若当前节点的值不满足条件，则不是 BST
    if root.Val <= min || root.Val >= max {
        return false
    }
    // 递归验证左子树和右子树
    return dfs(root.Left, min, root.Val) && dfs(root.Right, root.Val, max)
}

// 迭代实现
func isValidBST_1(root *TreeNode) bool {
    stack := []*TreeNode{}
    prev := math.MinInt64
    node := root

    for node != nil || len(stack) > 0 {
        // 遍历左子树
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        // 访问当前节点
        if node.Val <= prev {
            return false
        }
        prev = node.Val
        // 遍历右子树
        node = node.Right
    }

    return true
}

func main() {
    // 测试用例
    testCases := []struct {
        values   []int
        expected bool
    }{
        {
            values:   []int{2,1,3},
            expected: true,
        },
        {
            values:   []int{5,1,4,-1,-1,3,6},
            expected: false,
        },
    }

    for i, tc := range testCases {
        root := createTree(tc.values)
        fmt.Printf("Test Case %d, Input: values = %v\n", i+1, printTree(root))
        result := isValidBST(root)

        if result == tc.expected {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
        }
    }
}
#leetcode
leetcode98：验证二叉搜索树
https://lcf163.github.io/2024/03/10/leetcode98：验证二叉搜索树/
作者
乘风的小站
发布于
2024年3月10日
许可协议