-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0098.java
More file actions
140 lines (124 loc) · 4.55 KB
/
Copy pathSolution0098.java
File metadata and controls
140 lines (124 loc) · 4.55 KB
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
// 98. 验证二叉搜索树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/*
有效二叉搜索树定义如下：
1、节点的左子树只包含 小于 当前节点的数。
2、节点的右子树只包含 大于 当前节点的数。
3、所有左子树和右子树自身必须也是二叉搜索树。
*/
/*
中序遍历：
1、方法功能：入参是一个节点，判断当前节点是否比前一节点大，不是则返回false，是则返回true
2、终止条件：节点为空时返回true，才能继续遍历不为空的节点
3、单节点处理过程和返回结果：判断当前节点是否比前一节点大，不是则返回false，是则保存当前节点值，并返回true
4、递归调用：左右节点需要同样的操作，因此调用同样的方法处理，获取结果
5、递归顺序：中序遍历，根节点的处理依赖左节点的值，右节点的处理依赖根节点的值。需要中序遍历有序地保存前一节点值，给下一节点判断
6、使用递归调用结果和返回结果：
1）左节点不满足则返回false，满足则继续判断根节点；
2）根节点不满足则返回false，满足则继续判断右节点；
3）右节点不满足则返回false，满足则返回true，即直接返回右节点处理结果即可
*/
class Solution {
private long pre = Long.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);
}
}
/*
递归：
1、方法功能：入参是节点、最小值、最大值，判断节点值是否有效，即是否满足 min < val < max，有效返回true，无效返回false
2、终止条件：节点为空返回true
3、单节点处理过程和返回结果：判断节点值是否有效，即是否满足 min < val < max，有效效返回true，无效返回false
4、递归调用：左右节点需要同样的操作，因此调用同样的方法处理，获取结果
5、递归顺序：前序遍历，左右节点的处理依赖根节点的值，所以要先处理根节点，再处理左右节点
6、使用递归调用结果和返回结果：左右节点同时有效则返回true，否则返回false
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
private boolean isValid(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) {
return true;
}
if (min != null && root.val <= min.val) {
return false;
}
if (max != null && root.val >= max.val) {
return false;
}
return isValid(root.left, min, root) && isValid(root.right, root, max);
}
}
/*
“94. 二叉树的中序遍历”，中序遍历存入列表，再遍历判断是否升序
*/
class Solution {
public List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inorderTraversal(root);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) <= list.get(i - 1)) {
return false;
}
}
return true;
}
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
}
/*
迭代：“94. 二叉树的中序遍历”，中序遍历过程更新保存前一节点值，当前节点值小于等于前一节点值，则无效，否则有效
*/
class Solution {
public boolean isValidBST(TreeNode root) {
long pre = Long.MIN_VALUE;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur.val <= pre) {
return false;
}
pre = cur.val;
cur = cur.right;
}
}
return true;
}
}