Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdf9836e

Browse files
author
haotf
committed
二叉搜索树
1 parentdeb945d commitdf9836e

9 files changed

+342
-0
lines changed

‎.gitignore‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
.vscode
2+
log
Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/*
2+
* @lc app=leetcode.cn id=1038 lang=java
3+
*
4+
* [1038] 把二叉搜索树转换为累加树
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
25+
privateintres =0;
26+
27+
publicTreeNodebstToGst(TreeNoderoot) {
28+
returntraverse(root);
29+
}
30+
31+
privateTreeNodetraverse(TreeNoderoot) {
32+
if (root ==null)
33+
returnnull;
34+
traverse(root.right);
35+
res =res +root.val;
36+
root.val =res;
37+
traverse(root.left);
38+
returnroot;
39+
}
40+
}
41+
// @lc code=end
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
/*
2+
* @lc app=leetcode.cn id=230 lang=java
3+
*
4+
* [230] 二叉搜索树中第K小的元素
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
privateintrank =0;
25+
26+
publicintkthSmallest(TreeNoderoot,intk) {
27+
returntraverse(root,k).val;
28+
}
29+
30+
privateTreeNodetraverse(TreeNoderoot,intk) {
31+
if (root ==null)
32+
returnnull;
33+
TreeNodeleft =traverse(root.left,k);
34+
if (left !=null)
35+
returnleft;
36+
37+
rank++;
38+
if (rank ==k) {
39+
returnroot;
40+
}
41+
TreeNoderight =traverse(root.right,k);
42+
returnright;
43+
}
44+
}
45+
// @lc code=end
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
/*
2+
* @lc app=leetcode.cn id=450 lang=java
3+
*
4+
* [450] 删除二叉搜索树中的节点
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
publicTreeNodedeleteNode(TreeNoderoot,intkey) {
25+
returntraverse(root,key);
26+
}
27+
28+
privateTreeNodetraverse(TreeNoderoot,intkey) {
29+
if (root ==null)
30+
returnnull;
31+
if (root.val ==key) {
32+
if (root.left ==null &&root.right ==null)
33+
returnnull;
34+
if (root.left !=null &&root.right ==null)
35+
returnroot.left;
36+
if (root.right !=null &&root.left ==null)
37+
returnroot.right;
38+
if (root.left !=null &&root.right !=null) {
39+
TreeNodetmp =root.right;
40+
while (tmp.left !=null) {
41+
tmp =tmp.left;
42+
}
43+
tmp.right =deleteNode(root.right,tmp.val);
44+
tmp.left =root.left;
45+
returntmp;
46+
}
47+
}
48+
if (root.val >key) {
49+
root.left =traverse(root.left,key);
50+
}else {
51+
root.right =traverse(root.right,key);
52+
}
53+
returnroot;
54+
}
55+
}
56+
// @lc code=end
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
* @lc app=leetcode.cn id=538 lang=java
3+
*
4+
* [538] 把二叉搜索树转换为累加树
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
privateintres =0;
25+
26+
publicTreeNodeconvertBST(TreeNoderoot) {
27+
returntraverse(root);
28+
}
29+
30+
privateTreeNodetraverse(TreeNoderoot) {
31+
if (root ==null)
32+
returnnull;
33+
traverse(root.right);
34+
res =res +root.val;
35+
root.val =res;
36+
traverse(root.left);
37+
returnroot;
38+
}
39+
}
40+
// @lc code=end

‎652.寻找重复的子树.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
importjava.util.ArrayList;
2+
importjava.util.HashMap;
3+
importjava.util.List;
4+
importjava.util.Map;
5+
6+
/*
7+
* @lc app=leetcode.cn id=652 lang=java
8+
*
9+
* [652] 寻找重复的子树
10+
*/
11+
12+
// @lc code=start
13+
/**
14+
* Definition for a binary tree node.
15+
* public class TreeNode {
16+
* int val;
17+
* TreeNode left;
18+
* TreeNode right;
19+
* TreeNode() {}
20+
* TreeNode(int val) { this.val = val; }
21+
* TreeNode(int val, TreeNode left, TreeNode right) {
22+
* this.val = val;
23+
* this.left = left;
24+
* this.right = right;
25+
* }
26+
* }
27+
*/
28+
classSolution {
29+
privateList<TreeNode>list =newArrayList<>();
30+
privateMap<String,Integer>map =newHashMap<String,Integer>();
31+
32+
publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot) {
33+
traverse(root);
34+
returnlist;
35+
}
36+
37+
privateStringtraverse(TreeNoderoot) {
38+
if (root ==null)
39+
return"#";
40+
Stringstr =traverse(root.left) +',' +traverse(root.right) +',' +root.val;
41+
if (map.getOrDefault(str,0) ==1) {
42+
list.add(root);
43+
}
44+
map.put(str,map.getOrDefault(str,0) +1);
45+
returnstr;
46+
}
47+
}
48+
// @lc code=end
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/*
2+
* @lc app=leetcode.cn id=700 lang=java
3+
*
4+
* [700] 二叉搜索树中的搜索
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
publicTreeNodesearchBST(TreeNoderoot,intval) {
25+
if (root ==null)
26+
returnnull;
27+
if (root.val ==val)
28+
returnroot;
29+
if (root.val >val) {
30+
returnsearchBST(root.left,val);
31+
}else {
32+
returnsearchBST(root.right,val);
33+
}
34+
}
35+
}
36+
// @lc code=end
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/*
2+
* @lc app=leetcode.cn id=701 lang=java
3+
*
4+
* [701] 二叉搜索树中的插入操作
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
publicTreeNodeinsertIntoBST(TreeNoderoot,intval) {
25+
if (root ==null)
26+
returnnewTreeNode(val);
27+
if (root.val >val) {
28+
root.left =insertIntoBST(root.left,val);
29+
}elseif (root.val <val) {
30+
root.right =insertIntoBST(root.right,val);
31+
}
32+
returnroot;
33+
}
34+
}
35+
// @lc code=end

‎98.验证二叉搜索树.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
* @lc app=leetcode.cn id=98 lang=java
3+
*
4+
* [98] 验证二叉搜索树
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* Definition for a binary tree node.
10+
* public class TreeNode {
11+
* int val;
12+
* TreeNode left;
13+
* TreeNode right;
14+
* TreeNode() {}
15+
* TreeNode(int val) { this.val = val; }
16+
* TreeNode(int val, TreeNode left, TreeNode right) {
17+
* this.val = val;
18+
* this.left = left;
19+
* this.right = right;
20+
* }
21+
* }
22+
*/
23+
classSolution {
24+
publicbooleanisValidBST(TreeNoderoot) {
25+
returnvalid(root,null,null);
26+
}
27+
28+
privatebooleanvalid(TreeNoderoot,TreeNodemax,TreeNodemin) {
29+
if (root ==null)
30+
returntrue;
31+
if (max !=null &&max.val <=root.val)
32+
returnfalse;
33+
if (min !=null &&min.val >=root.val)
34+
returnfalse;
35+
36+
returnvalid(root.left,root,min) &&valid(root.right,max,root);
37+
}
38+
}
39+
// @lc code=end

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp