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

Commitdeb945d

Browse files
author
haotf
committed
构造二叉树
1 parentf025e1f commitdeb945d

7 files changed

+346
-0
lines changed
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
* @lc app=leetcode.cn id=105 lang=java
3+
*
4+
* [105] 从前序与中序遍历序列构造二叉树
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+
publicTreeNodebuildTree(int[]preorder,int[]inorder) {
25+
returntraverse(preorder,0,preorder.length -1,inorder,0,inorder.length -1);
26+
}
27+
28+
privateTreeNodetraverse(int[]preorder,intpStart,intpEnd,int[]inorder,intiStart,intiEnd) {
29+
if (pEnd <pStart ||iEnd <iStart)
30+
returnnull;
31+
32+
introot =preorder[pStart];
33+
intindex =getMaxIndex(inorder,iStart,iEnd,root);
34+
intgap =index -iStart;
35+
36+
TreeNodeleft =traverse(preorder,pStart +1,pStart +gap,inorder,iStart,index -1);
37+
TreeNoderight =traverse(preorder,pStart +gap +1,pEnd,inorder,index +1,iEnd);
38+
39+
TreeNodenode =newTreeNode(root);
40+
node.left =left;
41+
node.right =right;
42+
returnnode;
43+
}
44+
45+
privateintgetMaxIndex(int[]nums,intstart,intend,intmax) {
46+
intindex =0;
47+
for (inti =start;i <=end;i++) {
48+
if (nums[i] ==max) {
49+
max =nums[i];
50+
index =i;
51+
break;
52+
}
53+
}
54+
returnindex;
55+
}
56+
}
57+
// @lc code=end
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
* @lc app=leetcode.cn id=106 lang=java
3+
*
4+
* [106] 从中序与后序遍历序列构造二叉树
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+
publicTreeNodebuildTree(int[]inorder,int[]postorder) {
25+
returntraverse(inorder,0,inorder.length -1,postorder,0,postorder.length -1);
26+
}
27+
28+
privateTreeNodetraverse(int[]inorder,intiStart,intiEnd,int[]postorder,intpStart,intpEnd) {
29+
if (pEnd <pStart ||iEnd <iStart)
30+
returnnull;
31+
32+
introot =postorder[pEnd];
33+
intindex =getMaxIndex(inorder,iStart,iEnd,root);
34+
intgap =index -iStart;
35+
36+
TreeNodeleft =traverse(inorder,iStart,index -1,postorder,pStart,pStart +gap -1);
37+
TreeNoderight =traverse(inorder,index +1,iEnd,postorder,pStart +gap,pEnd -1);
38+
39+
TreeNodenode =newTreeNode(root);
40+
node.left =left;
41+
node.right =right;
42+
returnnode;
43+
}
44+
45+
privateintgetMaxIndex(int[]nums,intstart,intend,intmax) {
46+
intindex =0;
47+
for (inti =start;i <=end;i++) {
48+
if (nums[i] ==max) {
49+
max =nums[i];
50+
index =i;
51+
break;
52+
}
53+
}
54+
returnindex;
55+
}
56+
}
57+
// @lc code=end

‎114.二叉树展开为链表.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
* @lc app=leetcode.cn id=114 lang=java
3+
*
4+
* [114] 二叉树展开为链表
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+
publicvoidflatten(TreeNoderoot) {
25+
if (root ==null)
26+
return;
27+
TreeNodeparent =newTreeNode();
28+
traverse(root,parent);
29+
}
30+
31+
privateTreeNodetraverse(TreeNoderoot,TreeNodeparent) {
32+
if (root ==null)
33+
returnparent;
34+
parent.right =root;
35+
parent =parent.right;
36+
TreeNodeleft =parent.left;
37+
TreeNoderight =parent.right;
38+
parent.left =null;
39+
parent =traverse(left,parent);
40+
parent =traverse(right,parent);
41+
returnparent;
42+
}
43+
}
44+
// @lc code=end
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/*
2+
* @lc app=leetcode.cn id=116 lang=java
3+
*
4+
* [116] 填充每个节点的下一个右侧节点指针
5+
*/
6+
7+
// @lc code=start
8+
/*
9+
// Definition for a Node.
10+
class Node {
11+
public int val;
12+
public Node left;
13+
public Node right;
14+
public Node next;
15+
16+
public Node() {
17+
}
18+
19+
public Node(int _val) {
20+
val = _val;
21+
}
22+
23+
public Node(int _val, Node _left, Node _right, Node _next) {
24+
val = _val;
25+
left = _left;
26+
right = _right;
27+
next = _next;
28+
}
29+
};
30+
*/
31+
32+
classSolution {
33+
publicNodeconnect(Noderoot) {
34+
if (root ==null) {
35+
returnroot;
36+
}
37+
connectTwo(root.left,root.right);
38+
returnroot;
39+
}
40+
41+
privatevoidconnectTwo(Nodeleft,Noderight) {
42+
if (left ==null ||right ==null) {
43+
return;
44+
}
45+
left.next =right;
46+
connectTwo(left.left,left.right);
47+
connectTwo(left.right,right.left);
48+
connectTwo(right.left,right.right);
49+
}
50+
}
51+
// @lc code=end

‎654.最大二叉树.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
* @lc app=leetcode.cn id=654 lang=java
3+
*
4+
* [654] 最大二叉树
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+
publicTreeNodeconstructMaximumBinaryTree(int[]nums) {
25+
returntraverse(nums,0,nums.length -1);
26+
}
27+
28+
privateTreeNodetraverse(int[]nums,intstart,intend) {
29+
if (end <start)
30+
returnnull;
31+
// 获取最大值的key、value
32+
int[]values =getMaxKeyVal(nums,start,end);
33+
intmax =values[0];
34+
intindex =values[1];
35+
// 递归处理左右节点
36+
TreeNodeleft =traverse(nums,start,index -1);
37+
TreeNoderight =traverse(nums,index +1,end);
38+
39+
TreeNodenode =newTreeNode(max);
40+
node.left =left;
41+
node.right =right;
42+
returnnode;
43+
}
44+
45+
privateint[]getMaxKeyVal(int[]nums,intstart,intend) {
46+
intmax =Integer.MIN_VALUE;
47+
intindex =0;
48+
for (inti =start;i <=end;i++) {
49+
if (nums[i] >max) {
50+
max =nums[i];
51+
index =i;
52+
}
53+
}
54+
returnnewint[] {max,index };
55+
}
56+
}
57+
// @lc code=end
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
/*
2+
* @lc app=leetcode.cn id=889 lang=java
3+
*
4+
* [889] 根据前序和后序遍历构造二叉树
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+
publicTreeNodeconstructFromPrePost(int[]preorder,int[]postorder) {
25+
returntraverse(preorder,0,preorder.length -1,postorder,0,postorder.length -1);
26+
}
27+
28+
privateTreeNodetraverse(int[]preorder,intpreStart,intpreEnd,int[]postorder,intpostStart,intpostEnd) {
29+
if (preEnd <preStart ||postEnd <postStart)
30+
returnnull;
31+
if (preEnd ==preStart) {
32+
returnnewTreeNode(preorder[preStart]);
33+
}
34+
35+
intleftRootVal =preorder[preStart +1];
36+
intindex =getMaxIndex(postorder,postStart,postEnd,leftRootVal);
37+
intleftSize =index -postStart +1;
38+
39+
TreeNodeleft =traverse(preorder,preStart +1,preStart +leftSize,postorder,postStart,index);
40+
TreeNoderight =traverse(preorder,preStart +leftSize +1,preEnd,postorder,index +1,postEnd -1);
41+
42+
TreeNodenode =newTreeNode(preorder[preStart]);
43+
node.left =left;
44+
node.right =right;
45+
returnnode;
46+
}
47+
48+
privateintgetMaxIndex(int[]nums,intstart,intend,intmax) {
49+
intindex =0;
50+
for (inti =start;i <=end;i++) {
51+
if (nums[i] ==max) {
52+
max =nums[i];
53+
index =i;
54+
break;
55+
}
56+
}
57+
returnindex;
58+
}
59+
}
60+
// @lc code=end

‎Node.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
classNode {
2+
publicintval;
3+
publicNodeleft;
4+
publicNoderight;
5+
publicNodenext;
6+
7+
publicNode() {
8+
}
9+
10+
publicNode(int_val) {
11+
val =_val;
12+
}
13+
14+
publicNode(int_val,Node_left,Node_right,Node_next) {
15+
val =_val;
16+
left =_left;
17+
right =_right;
18+
next =_next;
19+
}
20+
};

0 commit comments

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