做网站需要什么硬件,台州seo排名优化,wordpress 网站地址,广州seo网站管理概述
关于面试中常见的其他二叉树算法题#xff0c;参考面试算法之二叉树(Java)。二叉树的定义#xff08;注意到有使用lombok提供的两个注解#xff09;#xff1a;
lombok.Data
lombok.AllArgsConstructor
private static class TreeNode {private TreeNode left;priva…概述
关于面试中常见的其他二叉树算法题参考面试算法之二叉树(Java)。二叉树的定义注意到有使用lombok提供的两个注解
lombok.Data
lombok.AllArgsConstructor
private static class TreeNode {private TreeNode left;private TreeNode right;private final int val;TreeNode(int x) {this.val x;}
}将有序数组转换为二叉搜索树
给定一个升序排序的整数数组nums将其转换为一棵高度平衡的二叉搜索树。来自LeetCode
分析给定一个有序数组转换成二叉搜索树即左子树小于根节点根节点小于右子树满足条件的二叉搜索树显然不止一种。
一般情况下大多数人都会考虑取数组的中间元素作为根节点。为啥选择中间元素为了确保得到的二叉树的高度差尽可能小。如果数组的元素个数是奇数根节点可以唯一确定如果是偶数则根节点不唯一。所以
如果题目没有限定高度平衡的二叉树则得到的二叉树将会更多。最差的情况就是退化成仅有根节点和左子树或右子树的二叉树即退化成类似链表的结构。
采用递归的方法
public static TreeNode sortedArrayToBST(int[] nums) {return traversal(nums, 0, nums.length - 1);
}private static TreeNode traversal(int[] nums, int left, int right) {if (left right) {// 叶子节点return null;}int mid left ((right - left) / 2);TreeNode node new TreeNode(nums[mid]);node.left traversal(nums, left, mid - 1);node.right traversal(nums, mid 1, right);return node;
}从中序与后序遍历序列构造二叉树
来自LeetCode
public static TreeNode buildTree(int[] inOrder, int[] postOrder) {return helper(inOrder, postOrder, postOrder.length - 1, 0, inOrder.length - 1);
}private static TreeNode helper(int[] inOrder, int[] postOrder, int postEnd, int inStart, int inEnd) {if (inStart inEnd) {return null;}int currentVal postOrder[postEnd];TreeNode current new TreeNode(currentVal);int inIndex 0;for (int i inStart; i inEnd; i) {if (inOrder[i] currentVal) {inIndex i;}}TreeNode left helper(inOrder, postOrder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);TreeNode right helper(inOrder, postOrder, postEnd - 1, inIndex 1, inEnd);current.left left;current.right right;return current;
}序列化
递归的思想采用前序遍历对空节点需要特殊处理使用任何占位符都可
public static String serialize(TreeNode root) {StringBuilder sb new StringBuilder();serializeHelper(root, sb);return sb.substring(0, sb.length() - 1);
}private static void serializeHelper(TreeNode node, StringBuilder sb) {if (node null) {sb.append(#,); // 空节点return;}sb.append(node.val).append(,);serializeHelper(node.left, sb);serializeHelper(node.right, sb);
}反序列化
能否从序列化后的字符串反序列化得到一棵树呢 答案是可以的。前提是知道对空节点的处理填位字符串策略节点的间隔字符策略。
能否从序列化后的字符串反序列化得到原始的二叉树 答案是不一定如果想要反序列化得到原始的二叉树有一些前提条件
序列化方案是前序、中序还是后序对空节点的处理策略节点的间隔字符策略
public static TreeNode deserialize(String data) {LinkedListString nodes new LinkedList(Arrays.asList(data.split(,)));return deserializeHelper(nodes);
}private static TreeNode deserializeHelper(LinkedListString nodes) {String val nodes.removeFirst();if (val.equals(#)) {return null;}TreeNode node new TreeNode(Integer.parseInt(val));node.left deserializeHelper(nodes);node.right deserializeHelper(nodes);return node;
}测试方法
public static void main(String[] args) {TreeNode head init();String s serialize(head);// TreeNode.toString()方法String b deserialize(s).toString();System.out.println(序列化 s);System.out.println(反序列化 b);
}附TreeNode.toString()方法
Override
public String toString() {return toString(this);
}public String toString(TreeNode r) {if (r null) {return #;} else {return r.val , toString(r.left) , toString(r.right);}
}输出
序列化8,4,2,#,1,#,#,3,#,#,7,#,6,5,#,#,#
反序列化8,4,2,#,1,#,#,3,#,#,7,#,6,5,#,#,#结论
已知序列化方案和空节点处理策略后可唯一反序列化得到原始二叉树二叉树的打印方法里对空节点的处理策略保持一致且间隔符都是,则两个字符串相等
进阶
如果不知道序列化方案如何反序列化得到二叉树
结论可以反序列化但是不一定是原始的二叉树所以这个反序列化也没有任何意义。
为了解决这个问题有几个选择
使用包含遍历顺序信息的序列化格式 在序列化字符串中包含遍历顺序信息。例如在字符串前面加上遍历顺序的标识符如P表示前序(Pre-order)I表示中序(In-order)O表示后序(post-Order)。双序列化 使用两种不同的遍历顺序分别序列化树并将两个序列化结果一起保存。两种方案字符|以分隔。例如使用前序和中序或后序和中序。
其中方案二基于这样一个已被证实的结论若存在对同一棵二叉树的两种不一样的遍历序列化方案则一定可以唯一确定这棵二叉树。
/*** 序列化二叉树前序和中序*/
public static String serialize1(TreeNode root) {StringBuilder preOrder new StringBuilder();StringBuilder inOrder new StringBuilder();serializePreOrder(root, preOrder);serializeInOrder(root, inOrder);return preOrder.toString() | inOrder.toString(); // 使用 | 作为分隔符
}private static void serializePreOrder(TreeNode node, StringBuilder sb) {if (node null) {sb.append(#,);return;}sb.append(node.val).append(,);serializePreOrder(node.left, sb);serializePreOrder(node.right, sb);
}private static void serializeInOrder(TreeNode node, StringBuilder sb) {if (node null) {sb.append(#,);return;}serializeInOrder(node.left, sb);sb.append(node.val).append(,);serializeInOrder(node.right, sb);
}/*** 反序列化二叉树*/
public static TreeNode deserialize1(String data) {// 需预知的信息两个字符串的分隔符String[] parts data.split(\\|);// 需预知的信息序列化的间隔符LinkedListString preOrderNodes new LinkedList(Arrays.asList(parts[0].split(,)));LinkedListString inOrderNodes new LinkedList(Arrays.asList(parts[1].split(,)));return buildTree(preOrderNodes, inOrderNodes);
}private static TreeNode buildTree(LinkedListString preOrderNodes, LinkedListString inOrderNodes) {// 需预知的信息对空节点的处理策略if (preOrderNodes.isEmpty() || preOrderNodes.peek().equals(#)) {preOrderNodes.poll();inOrderNodes.poll();return null;}String rootVal preOrderNodes.poll();TreeNode root new TreeNode(Integer.parseInt(rootVal));int inOrderIndex inOrderNodes.indexOf(rootVal);root.left buildTree(preOrderNodes, new LinkedList(inOrderNodes.subList(0, inOrderIndex)));root.right buildTree(preOrderNodes, new LinkedList(inOrderNodes.subList(inOrderIndex 1, inOrderNodes.size())));inOrderNodes.poll();return root;
}可以看出这两个方案还是得提前知道一些规则信息。事实上网络通信就是一个包含序列化和反序列化的过程如果不知道序列化规则即协议信息则反序列化几乎没有意义。
参考
