题目描述： 请实现两个函数，分别用来序列化和反序列化二叉树 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。 题目分析： 题目需求是实现一个函数实现二叉树的序列化，将一棵树使用唯一的一个字符串进行表示，每个数值后面使用！结束（主要是为了区分值例如12！3！表示一个节点值为12，一个节点值为3），每一个#表示空节点。本质为二叉树的遍历，本次采用递归调用的先序遍历。 序列化二叉树代码如下：
String Serialize(TreeNode root) { if(root==null) { return ""; } //采用StringBuilder，比StringBuffer和+号拼接更快，单线程不安全 StringBuilder sb=new StringBuilder(); return fore(sb,root); } String fore(StringBuilder sb,TreeNode curnode) { //每次将传入的节点拼接 TreeNode tmp=curnode; sb.append(curnode.val); sb.append("!"); //递归将左子树拼接 if(curnode.left!=null) { fore(sb,curnode.left); }else { sb.append("#"); sb.append("!"); } //递归将右子树拼接 if(curnode.right!=null) { fore(sb,curnode.right); }else { sb.append("#"); sb.append("!"); } return sb.toString(); }反序列化二叉树代码如下：
TreeNode Deserialize(String str) { if(str.length()<=0) { return null; } //根据！拆分，将字符串转换成字符串数组 String[] split = str.split("!"); //使用额外的控件队列进行树的构建 Queue<TreeNode> s=new LinkedList<>(); int i=0; while(i<split.length) { TreeNode tree=new TreeNode(-1); //将中间的数值节点建立并入列 if(!split[i].equals("#")) { tree=new TreeNode(Integer.valueOf(split[i])); }else { tree=null; } s.add(tree); i++; } return ReconPreOrder(s); } TreeNode ReconPreOrder(Queue<TreeNode> queue) { //从队列取出头元素并删除 TreeNode value = queue.poll(); //如果没数据则退出递归 if (value==null) return null; //创建一个新的结点并给它赋值 TreeNode head = value; //递归得到当前结点的左孩子（遇到“#”则结束） head.left = ReconPreOrder(queue); //递归得到当前结点的右孩子（遇到“#”则结束） head.right = ReconPreOrder(queue); //返回这个二叉树的头结点 return head; } }题目二描述： 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。 题目二分析： 二叉搜索树，也叫二叉排序树，其左孩子小于父节点，有孩子大于父节点，因此采用部分中序遍历的方式进行查找。 代码如下：
public class Solution { TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null||k<=0) { return null; } return diGui(pRoot,k); } int count = 0; TreeNode diGui(TreeNode curnode,int k) { TreeNode newnode=new TreeNode(0); //递归从左边找到是否有k各节点 if(curnode.left!=null){ newnode=diGui(curnode.left,k); if(k == count) { return newnode; } } //中间节点是否符合到达k count++; newnode=curnode; if(k == count) { return curnode; } //递归遍历寻找右边的节点是否到达k if(curnode.right!=null ) { newnode=diGui(curnode.right,k); if(k == count) { return newnode; } } //遍历树的所有节点也没有k则返回null return null; } }