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

Commit599cf77

Browse files
author
haotf
committed
二叉搜索树
1 parentdf9836e commit599cf77

8 files changed

+326
-0
lines changed
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/*
2+
* @lc app=leetcode.cn id=1373 lang=java
3+
*
4+
* [1373] 二叉搜索子树的最大键值和
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+
privateintmaxSum =0;
25+
privateintsumIndex =0;
26+
privateintmaxIndex =1;
27+
privateintminIndex =2;
28+
29+
publicintmaxSumBST(TreeNoderoot) {
30+
traverse(root);
31+
returnmaxSum;
32+
}
33+
34+
privateint[]traverse(TreeNoderoot) {
35+
if (root ==null)
36+
returnnewint[] {0,Integer.MIN_VALUE,Integer.MAX_VALUE };
37+
int[]left =traverse(root.left);
38+
int[]right =traverse(root.right);
39+
40+
int[]result =newint[3];
41+
// 二叉搜索树
42+
if (root.val >left[maxIndex] &&root.val <right[minIndex]) {
43+
result[sumIndex] =left[sumIndex] +right[sumIndex] +root.val;
44+
result[maxIndex] =Math.max(root.val,right[maxIndex]);
45+
result[minIndex] =Math.min(root.val,left[minIndex]);
46+
maxSum =Math.max(maxSum,result[sumIndex]);
47+
}else {
48+
returnnewint[] {0,Integer.MAX_VALUE,Integer.MIN_VALUE };
49+
}
50+
returnresult;
51+
}
52+
}
53+
// @lc code=end
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* @lc app=leetcode.cn id=222 lang=java
3+
*
4+
* [222] 完全二叉树的节点个数
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+
publicintcountNodes(TreeNoderoot) {
25+
if (root ==null)
26+
return0;
27+
return1 +countNodes(root.left) +countNodes(root.right);
28+
}
29+
}
30+
// @lc code=end
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/*
2+
* @lc app=leetcode.cn id=236 lang=java
3+
*
4+
* [236] 二叉树的最近公共祖先
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(int x) { val = x; }
15+
* }
16+
*/
17+
classSolution {
18+
publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq) {
19+
if (root ==null)
20+
returnnull;
21+
if (root ==p ||root ==q)
22+
returnroot;
23+
TreeNodeleft =lowestCommonAncestor(root.left,p,q);
24+
TreeNoderight =lowestCommonAncestor(root.right,p,q);
25+
if (left ==null &&right ==null)
26+
returnnull;
27+
if (left !=null &&right !=null)
28+
returnroot;
29+
returnleft !=null ?left :right;
30+
}
31+
}
32+
// @lc code=end
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
importjava.util.ArrayList;
2+
importjava.util.Arrays;
3+
importjava.util.List;
4+
5+
/*
6+
* @lc app=leetcode.cn id=297 lang=java
7+
*
8+
* [297] 二叉树的序列化与反序列化
9+
*/
10+
11+
// @lc code=start
12+
/**
13+
* Definition for a binary tree node.
14+
* public class TreeNode {
15+
* int val;
16+
* TreeNode left;
17+
* TreeNode right;
18+
* TreeNode(int x) { val = x; }
19+
* }
20+
*/
21+
classCodec {
22+
23+
// Encodes a tree to a single string.
24+
publicStringserialize(TreeNoderoot) {
25+
if (root ==null)
26+
return"#";
27+
returnroot.val +"," +serialize(root.left) +"," +serialize(root.right);
28+
}
29+
30+
// Decodes your encoded data to tree.
31+
publicTreeNodedeserialize(Stringdata) {
32+
String[]datas =data.split(",");
33+
ArrayList<String>nodes =newArrayList<String>(Arrays.asList(datas));
34+
returndeserialize(nodes);
35+
}
36+
37+
privateTreeNodedeserialize(List<String>nodes) {
38+
if (nodes.isEmpty())
39+
returnnull;
40+
Stringval =nodes.remove(0);
41+
if (val.equals("#"))
42+
returnnull;
43+
TreeNoderoot =newTreeNode(Integer.parseInt(val));
44+
root.left =deserialize(nodes);
45+
root.right =deserialize(nodes);
46+
returnroot;
47+
}
48+
}
49+
50+
// Your Codec object will be instantiated and called as such:
51+
// Codec ser = new Codec();
52+
// Codec deser = new Codec();
53+
// TreeNode ans = deser.deserialize(ser.serialize(root));
54+
// @lc code=end
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
importjava.util.Iterator;
2+
importjava.util.List;
3+
4+
/*
5+
* @lc app=leetcode.cn id=341 lang=java
6+
*
7+
* [341] 扁平化嵌套列表迭代器
8+
*/
9+
10+
// @lc code=start
11+
12+
// This is the interface that allows for creating nested lists.
13+
// You should not implement it, or speculate about its implementation
14+
15+
classNestedIteratorimplementsIterator<Integer> {
16+
17+
privateList<NestedInteger>list;
18+
19+
publicNestedIterator(List<NestedInteger>nestedList) {
20+
this.list =nestedList;
21+
}
22+
23+
@Override
24+
publicIntegernext() {
25+
returnthis.list.remove(0).getInteger();
26+
}
27+
28+
@Override
29+
publicbooleanhasNext() {
30+
if (this.list.isEmpty())
31+
returnfalse;
32+
33+
NestedIntegerfirst =this.list.get(0);
34+
while (first !=null && !first.isInteger()) {
35+
first =this.list.remove(0);
36+
List<NestedInteger>childs =first.getList();
37+
if (!childs.isEmpty()) {
38+
this.list.addAll(0,childs);
39+
}
40+
if (this.list.isEmpty()) {
41+
returnfalse;
42+
}
43+
first =this.list.get(0);
44+
}
45+
return !this.list.isEmpty();
46+
}
47+
}
48+
49+
/**
50+
* Your NestedIterator object will be instantiated and called as such:
51+
* NestedIterator i = new NestedIterator(nestedList);
52+
* while (i.hasNext()) v[f()] = i.next();
53+
*/
54+
// @lc code=end
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
importjava.util.ArrayList;
2+
importjava.util.List;
3+
4+
/*
5+
* @lc app=leetcode.cn id=95 lang=java
6+
*
7+
* [95] 不同的二叉搜索树 II
8+
*/
9+
10+
// @lc code=start
11+
/**
12+
* Definition for a binary tree node.
13+
* public class TreeNode {
14+
* int val;
15+
* TreeNode left;
16+
* TreeNode right;
17+
* TreeNode() {}
18+
* TreeNode(int val) { this.val = val; }
19+
* TreeNode(int val, TreeNode left, TreeNode right) {
20+
* this.val = val;
21+
* this.left = left;
22+
* this.right = right;
23+
* }
24+
* }
25+
*/
26+
classSolution {
27+
publicList<TreeNode>generateTrees(intn) {
28+
if (n ==0)
29+
returnnewArrayList<>();
30+
returntraverse(1,n);
31+
}
32+
33+
privateList<TreeNode>traverse(intstart,intend) {
34+
List<TreeNode>list =newArrayList<>();
35+
if (end <start) {
36+
list.add(null);
37+
returnlist;
38+
}
39+
40+
for (inti =start;i <=end;i++) {
41+
List<TreeNode>lList =traverse(start,i -1);
42+
List<TreeNode>rList =traverse(i +1,end);
43+
for (intl =0;l <lList.size();l++) {
44+
for (intr =0;r <rList.size();r++) {
45+
TreeNodenode =newTreeNode(i);
46+
node.left =lList.get(l);
47+
node.right =rList.get(r);
48+
list.add(node);
49+
}
50+
}
51+
}
52+
returnlist;
53+
}
54+
}
55+
// @lc code=end

‎96.不同的二叉搜索树.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* @lc app=leetcode.cn id=96 lang=java
3+
*
4+
* [96] 不同的二叉搜索树
5+
*/
6+
7+
// @lc code=start
8+
classSolution {
9+
privateint[][]memo;
10+
11+
publicintnumTrees(intn) {
12+
memo =newint[n +1][n +1];
13+
returncount(1,n);
14+
}
15+
16+
privateintcount(intstart,intend) {
17+
if (start >=end)
18+
return1;
19+
if (memo[start][end] !=0)
20+
returnmemo[start][end];
21+
22+
intsum =0;
23+
for (inti =start;i <=end;i++) {
24+
sum +=count(start,i -1) *count(i +1,end);
25+
}
26+
memo[start][end] =sum;
27+
returnsum;
28+
}
29+
}
30+
// @lc code=end

‎NestedInteger.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
importjava.util.List;
2+
3+
publicinterfaceNestedInteger {
4+
5+
// @return true if this NestedInteger holds a single integer, rather than a
6+
// nested list.
7+
publicbooleanisInteger();
8+
9+
// @return the single integer that this NestedInteger holds, if it holds a
10+
// single integer
11+
// Return null if this NestedInteger holds a nested list
12+
publicIntegergetInteger();
13+
14+
// @return the nested list that this NestedInteger holds, if it holds a nested
15+
// list
16+
// Return empty list if this NestedInteger holds a single integer
17+
publicList<NestedInteger>getList();
18+
}

0 commit comments

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