序列化二叉树&&二叉搜索树的第k个结点 - 好文

<>序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

<>解题思路

采用层序遍历，遍历二叉树时碰到null指针时，这些null指针被序列化为一个特殊的字符“#”。另外，结点之间的数值用逗号隔开

<>代码
import java.util.LinkedList; import java.util.Queue; /** * 剑指offer一刷：序列化二叉树 *
* @author User * @create 2019-06-11-22:21 */ /** *
序列化就是遍历二叉树为字符串；反序列化指的是依据字符串重新构造二叉树 *
采用层序遍历，遍历二叉树时碰到null指针时，这些null指针被序列化为一个特殊的字符“#” * 另外，结点之间的数值用逗号隔开。 */ public
class jzo61 { String Serialize(TreeNode root) { StringBuilder sb=new
StringBuilder(); Queue<TreeNode> queue=new LinkedList<TreeNode>(); if
(root!=null){ queue.add(root); } while (!queue.isEmpty()){ TreeNode
node=queue.poll(); if (node!=null){ queue.offer(node.left);
queue.offer(node.right); sb.append(node.val+","); }else{ sb.append("#"+","); }
} if (sb.length()!=0){ sb.deleteCharAt(sb.length()-1); } return sb.toString();
} TreeNode Deserialize(String str) { TreeNode head=null; if
(str==null||str.length()==0){ return head; } String[] nodes=str.split(",");
TreeNode[] treeNodes=new TreeNode[nodes.length]; for (int
i=0;i<nodes.length;i++){ if (!nodes[i].equals("#")){ treeNodes[i]=new
TreeNode(Integer.valueOf(nodes[i])); } } for (int
i=0,j=1;j<treeNodes.length;i++){ if (treeNodes[i]!=null){
treeNodes[i].left=treeNodes[j++]; treeNodes[i].right=treeNodes[j++]; } } return
treeNodes[0]; } public static void main(String[] args){ TreeNode node1=new
TreeNode(1); TreeNode node2=new TreeNode(2); TreeNode node3=new TreeNode(3);
TreeNode node4=new TreeNode(4); TreeNode node5=new TreeNode(5); TreeNode
node6=new TreeNode(6); TreeNode node7=new TreeNode(7); TreeNode node8=new
TreeNode(8); TreeNode node9=new TreeNode(9); node1.left=node2;
node1.right=node3; node2.left=node4; node2.right=node5; node3.left=node6;
node3.right=node7; node4.left=node8; node4.right=node9; jzo61 so=new jzo61();
System.out.println(so.Serialize(node1)); } }
<>二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

<>解题思路

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。所以，按照中序遍历顺序找到第k个结点就是结果。

<>代码
/** * 剑指offer一刷：二叉搜索树的第k个结点 * * @author User * @create 2019-06-12-21:45 */
import java.util.Stack; /** * 按照二叉树的中序遍历打印出来就是排序好的顺序 * 找到中序遍历后的第k个结点就是结果 */
public class jzo62 { int index=0; TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot != null){ //中序遍历寻找第k个 TreeNode node = KthNode(pRoot.left,k); if(node
!= null) return node; index ++; if(index == k) return pRoot; node =
KthNode(pRoot.right,k); if(node != null) return node; } return null; } TreeNode
KthNode1(TreeNode root, int k){ if (root==null||k==0){ return null; }
Stack<TreeNode> stack=new Stack<>(); int count =0; do { if (root!=null){
stack.push(root); root=root.left; }else { root=stack.pop(); count++; if
(count==k){ return root; } root=root.right; } }while
(root!=null||!stack.isEmpty()); return null; } public static void main(String[]
args){ TreeNode node1=new TreeNode(1); TreeNode node2=new TreeNode(2); TreeNode
node3=new TreeNode(3); TreeNode node4=new TreeNode(4); TreeNode node5=new
TreeNode(5); TreeNode node6=new TreeNode(6); TreeNode node7=new TreeNode(7);
TreeNode node8=new TreeNode(9); TreeNode node9=new TreeNode(10); TreeNode
node10=new TreeNode(11); TreeNode node11=new TreeNode(12); node7.left=node4;
node7.right=node9; node4.left=node2; node4.right=node6; node6.left=node5;
node2.left=node1; node2.right=node3; node9.left=node8; node9.right=node11;
node11.left=node10; jzo62 so=new jzo62();
System.out.println(so.KthNode(node7,4).val);
System.out.println(so.KthNode1(node7,4).val); } }

热门工具换一换