-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTreeNode.java
More file actions
136 lines (125 loc) · 4 KB
/
Copy pathTreeNode.java
File metadata and controls
136 lines (125 loc) · 4 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
package Entitys;
import BinaryTree.BinaryTreeMaxPathSum;
import com.sun.deploy.util.StringUtils;
import java.util.*;
/**
* @description: 描述
* @author: dekai.kong
* @date: 2019-01-08 11:21
* @from
*/
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode genTreeNode(int[] ints, int index){
TreeNode temp = new TreeNode();
if(index >= ints.length){
return null;
}
if(ints[index]==0||ints[index] == -1){
return null;
}else{
temp.val = ints[index];
if(2*index+1<ints.length){
temp.left = genTreeNode(ints,2*index+1);
temp.right = genTreeNode(ints,2*index+2);
}
}
return temp;
}
public static TreeNode genTreeNode(String data){
// int[] ints = new int[data.length()];
// for (int i =0;i<data.length();i++){
// String x = String.valueOf(data.charAt(i));
// ints[i] = Integer.parseInt("-".equals(x)? "-1" :x);
// }
String[] stris = data.split(",");
int[] ints = Arrays.stream(stris).mapToInt(Integer::parseInt).toArray();
return genTreeNode(ints,0);
}
/**
* tree转string 层序遍历
* @return
*/
public static String tree2String(TreeNode root){
if(root == null){
return "-1";
}
List<Integer> arrs = new ArrayList<>();
int place = -1;
Queue queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()){
TreeNode pop = (TreeNode)queue.poll();
int v = pop.val;
arrs.add(v);
if(pop.left!=null && pop.right!=null){
queue.add(pop.left);
queue.add(pop.right);
}else if (pop.left!=null){
queue.add(pop.left);
if(pop.left.left!=null || pop.left.right!=null){
queue.add(new TreeNode(place));
}
}else if(pop.right!=null){
queue.add(new TreeNode(place));
queue.add(pop.right);
}else if(pop.val!=-1 && !queue.isEmpty()){
queue.add(new TreeNode(place));
queue.add(new TreeNode(place));
}
}
String rst = "";
for (int i = 0; i < arrs.size(); i++) {
rst+=(arrs.get(i)+",");
}
return rst;
}
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null){return "#";}
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
StringBuilder ans=new StringBuilder();
while(q.size()>0){
TreeNode t=q.poll();
ans.append("#");
if(t!=null){
ans.append(t.val);
q.add(t.left);
q.add(t.right);
}
}
return ans.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("#")){return null;}
String s[]=data.split("#",-1);
TreeNode ans=new TreeNode(Integer.parseInt(s[1]));
Queue<TreeNode> q=new LinkedList<>();
q.add(ans);
for(int i=3;i<s.length;i+=2){
TreeNode t=q.poll();
if(s[i-1].length()>0){
t.left=new TreeNode(Integer.parseInt(s[i-1]));
q.add(t.left);
}
if(s[i].length()>0){
t.right=new TreeNode(Integer.parseInt(s[i]));
q.add(t.right);
}
}
return ans;
}
}
}