alg-tree

297 序列化/反序列化二叉树

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
private static final String spliter = ",";
private static final String NN = "X";

public String serialize(TreeNode root){
StringBuilder sb = new StringBuilder();
buildString(root,sb);
return sb.toString();
}

private void buildString(TreeNode node,StringBuilder sb){
if(node == null){
sb.append(NN).append(spliter);
}else{
sb.append(node.val).append(spliter);
buildString(node.left,sb);
buildString(node.right,sb);
}
}

public TreeNode deserialize(String data){
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}

private TreeNode buildTree(Deque<String> nodes){
String val = nodes.remove();
if(val.equals(NN))return null;
else{
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}

652 重复子树

114 Flatten Binary Tree to Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
in:
1
/ \
2 5
/ \ \
3 4 6
out:
1
\
2
\
3
\
4
\
5
\
6

用一个全局变量保存右边flatten好的根节点,移动到当前flatten节点的右边。
后序遍历,并且先右节点再左节点。

1
2
3
4
5
6
7
8
9
TreeNode prev = null;
public void flatten(TreeNode root) {
if(root == null)return;
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}

513. Find Bottom Left Tree Value

Input:

1
2
3
4
5
6
7
    1
/ \
2 3
/ / \
4 5 6
/
7

Output:
7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> que = new ArrayDeque<>();
que.add(root);
int rst = root.val;
while(!que.isEmpty()){
int size = que.size();
rst = que.peek().val;
while(size-- >0){
TreeNode tmp = que.poll();
if(tmp.left!=null)que.add(tmp.left);
if(tmp.right!=null)que.add(tmp.right);
}
}
return rst;
}