leetcode/code/lc297.java at master · mJackie/leetcode · GitHub

History

60 lines (55 loc) · 1.73 KB

Raw

package code;

import java.util.Arrays;

import java.util.Deque;

import java.util.LinkedList;

* 297. Serialize and Deserialize Binary Tree

* 题意：序列化，反序列化树

* 难度：Hard

* 分类：Tree, Design

* 思路：

* Tips：lc572 序列化的应用

public class lc297 {

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

public class Codec {

private static final String spliter = ",";

private static final String NN = "X";

// Encodes a tree to a single string.

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);

}

// Decodes your encoded data to tree.

public TreeNode deserialize(String data) {

Deque<String> nodes = new LinkedList<>();

nodes.addAll(Arrays.asList(data.split(spliter))); //split

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;

}

leetcode/code/lc297.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc297.java

Latest commit

History

Breadcrumbs

lc297.java

File metadata and controls