验证二叉搜索树
link：98. 验证二叉搜索树 - 力扣（LeetCode）
思路分析
搞清二叉搜索树的定义即可.(根节点的左子树比根节点小，右子树比根节点大且每个子树都满足)
但其实上述思路是是不对， 跑一下代码发现测试样例值通过了一部分.那是哪里出问题了？（烧烤）
比较的应该是左子树所有节点小于中间节点，右子树所有节点大于中间节点.
查资料发现二叉搜索树也可以为空
迭代
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
|
class Solution {
public boolean isValidBST(TreeNode root) {
return validBST(Long.MIN_VALUE, Long.MAX_VALUE, root);
}
boolean validBST(long lower, long upper, TreeNode root) {
if (root == null) {
return true;
}
if (root.val <= lower || root.val >= upper) {
return false;
}
return validBST(lower, root.val, root.left) && validBST(root.val, upper, root.right);
}
}
|
中序遍历
采用pre指针遍历对比记录前一个节点内容，进行中序遍历比较.
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
|
class Solution {
TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
if(root == null) {
return true;
}
boolean left = isValidBST(root.left);
if(pre != null && pre.val >= root.val) {
return false;
}
pre = root;
boolean right = isValidBST(root.right);
return left && right;
}
}
|
二叉搜索树的最小绝队差
link：530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
思路分析
和上一题一样，用一个指针记录遍历比较再用一个大数值记录结果即可.【注意取值】
中序遍历
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
|
class Solution {
TreeNode pre = null;
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null) {
return 0;
}
getMinimumDifference(root.left);
if(pre != null) {
int tmp = root.val - pre.val;
if(tmp < result) {
result = tmp;
}
}
pre = root;
getMinimumDifference(root.right);
return result;
}
}
|
二叉搜索树中的众数
link：501. 二叉搜索树中的众数 - 力扣（LeetCode）
思路分析
最直接就是直接遍历搜索，使用Map比较记录.但是这样就失去了搜索二叉树的意义.
所以我们还是选择中序遍历的方式，需要定义count（记录当前节点出现的次数）和maxCount（出现次数最多的节点），再定义一个pre作为记录节点方便比较.
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
|
class Solution {
List<Integer> res = new ArrayList<>();;
int count = 0;
int maxCount = 0;
TreeNode pre = null;
public int[] findMode(TreeNode root) {
findMode1(root);
int[] result = new int[res.size()];
for(int i = 0; i < res.size();i++) {
result[i] = res.get(i);
}
return result;
}
void findMode1(TreeNode root) {
if(root == null){
return;
}
findMode1(root.left);
if(pre == null || pre.val != root.val) {
count = 1;
}else {
count++;
}
if(count > maxCount) {
res.clear();
res.add(root.val);
maxCount = count;
}else if(count == maxCount) {
res.add(root.val);
}
pre = root;
findMode1(root.right);
}
}
|
二叉搜索树的最近公共祖先
link:236. 二叉树的最近公共祖先 - 力扣（LeetCode）
思路分析
可以使用两个栈来存储从根节点到 p 和 q 的路径，然后通过比较这两个路径来找到它们的最低公共祖先
栈
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
| private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
if (root == null || node == null) {
return false;
}
stack.push(root);
if (root == node) {
return true;
}
boolean flg = getPath(root.left, node, stack);
if (flg) {
return true;
}
boolean flg2 = getPath(root.right, node, stack);
if (flg2) {
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
Stack<TreeNode> stackP = new Stack<>();
Stack<TreeNode> stackQ = new Stack<>();
getPath(root, p, stackP);
getPath(root, q, stackQ);
int sizeP = stackP.size();
int sizeQ = stackQ.size();
if (sizeP > sizeQ) {
int size = sizeP - sizeQ;
while (size != 0) {
stackP.pop();
size--;
}
} else {
int size = sizeQ - sizeP;
while (size != 0) {
stackQ.pop();
size--;
}
}
while (!stackP.isEmpty() && !stackQ.isEmpty()) {
if (stackP.peek().equals(stackQ.peek())) {
return stackP.peek();
}
stackP.pop();
stackQ.pop();
}
return null;
}
|
DFS（后序遍历）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) {
return null;
} else if (left == null && right != null) {
return right;
} else if (left != null && right == null) {
return left;
} else {
return root;
}
}
|
