山东建设厅官方网站二建报名非国产手机浏览器
思路
- 通常存储二叉树是采用链式的非线性方式存储，而此题需要用线性的存储方式。思维不同。
- 首先确定遍历方式。将根节点作为第一个节点很方便，之后在遍历左子树和右子树，故可采取前序遍历和层次遍历。
- 其次，线性的字符串存储，需要用分割符来划分不同的节点，可以采用逗号作为节点分隔符。
- 然后，在链式存储中，由于左右子节点指针的存在，节点之间的关系可以通过指针指向来确定，树的结构也由此唯一确定，所以空节点一般不用考虑。而在线性存储结构中，没有指针确定节点之间的关系，所以需要考虑空节点，从而才能确定唯一的树结构。
前序遍历
非递归采用单栈实现
Java实现:
public class Codec {//前序遍历非递归public String serialize(TreeNode root){//空树if(root == null){return "";}// 用于遍历二叉树的辅助栈Deque<TreeNode> stack = new ArrayDeque<>();// 保存结果StringBuilder res = new StringBuilder();TreeNode curNode = root;while(curNode != null || !stack.isEmpty()){while(curNode != null){// 根res.append(String.valueOf(curNode.val));res.append(",");stack.offerLast(curNode);//左子树curNode = curNode.left;}res.append("null,");curNode = stack.pollLast();//右子树curNode = curNode.right;}res.append("null");// System.out.println("res: " + res);return res.toString();}public TreeNode deserialize(String data){if(data == ""){return null;}Deque<TreeNode> stack = new ArrayDeque<>();// 根据分隔符生成节点数组String[] nodeList = data.split(",");// 处理根节点TreeNode root = new TreeNode(Integer.parseInt(nodeList[0]));TreeNode curNode = root;int idx = 1;while(curNode != null || !stack.isEmpty()){while(curNode != null){stack.offerLast(curNode);if(!nodeList[idx].equals("null")){// 处理当前节点的左孩子curNode.left = new TreeNode(Integer.parseInt(nodeList[idx]));// stack.offerLast(curNode.left);}// 左子树curNode = curNode.left;idx++;}curNode = stack.pollLast();if(!nodeList[idx].equals("null")){// 处理当前节点的右孩子curNode.right = new TreeNode(Integer.parseInt(nodeList[idx]));// stack.offerLast(curNode.right);}// 有子树curNode = curNode.right;idx++;}return root;}
}
递归实现
Java代码：
public class Codec {// Encodes a tree to a single string.//线性结构存储二叉树public String serialize(TreeNode root) {//前序遍历递归实现if(root == null){return "null"; //空节点}String leftStr = serialize(root.left); //序列化左子树String rightStr = serialize(root.right); //序列化右子树return String.valueOf(root.val) + "," + leftStr + "," + rightStr;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] nodeStrs = data.split(","); //将字符串划分为字符数组int[] i = new int[]{0};return dfs(nodeStrs, i);}private TreeNode dfs(String[] nodeStrs, int[] i){String str = nodeStrs[i[0]];i[0]++; //堆区变量，能够实现递增遍历字符数组if("null".equals(str)){return null;}TreeNode node = new TreeNode(Integer.valueOf(str));node.left = dfs(nodeStrs, i);node.right = dfs(nodeStrs, i);return node;}
}
层次遍历
public class Codec {//层次遍历实现public String serialize(TreeNode root){StringBuilder res = new StringBuilder();//层次遍历辅助队列//Queue<TreeNode> queue = new ArrayDeque<>();Queue<TreeNode> queue = new LinkedList<>();if(root == null){return "";}queue.offer(root);while(!queue.isEmpty()){TreeNode curNode = queue.poll();//非空节点if(curNode != null){res.append(String.valueOf(curNode.val));//先将左右子树入队，等其出队(遍历到时)时再判断queue.offer(curNode.left);queue.offer(curNode.right);} else { //空节点res.append("null");}res.append(","); //添加节点区分分割符}return res.toString();}public TreeNode deserialize(String data){if(data == ""){return null;}String[] nodeList = data.split(",");//创建根节点TreeNode root = new TreeNode(Integer.parseInt(nodeList[0]));//层次遍历辅助队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int idx = 1; //用于遍历节点列表while(!queue.isEmpty()){TreeNode curNode = queue.poll();//创建左子树if(!nodeList[idx].equals("null")){curNode.left = new TreeNode(Integer.valueOf(nodeList[idx]));queue.offer(curNode.left);}idx++;//创建右子树if(!"null".equals(nodeList[idx])){curNode.right = new TreeNode(Integer.parseInt(nodeList[idx]));queue.offer(curNode.right);}++idx;}return root;}
}
历程：题目做得少，思考的少就需要多见识。代码需要多敲，考虑一题多解。递归和迭代都实现。