当前位置: 首页 > news >正文

有没人做阿里巴巴网站维护的营销网络怎么写

有没人做阿里巴巴网站维护的,营销网络怎么写,上海专业微信网站建设,江苏建站管理系统开发概述 关于面试中常见的其他二叉树算法题,参考面试算法之二叉树(Java)。二叉树的定义(注意到有使用lombok提供的两个注解): 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) {LinkedList<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));return deserializeHelper(nodes);
}private static TreeNode deserializeHelper(LinkedList<String> 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("\\|");// 需预知的信息:序列化的间隔符LinkedList<String> preOrderNodes = new LinkedList<>(Arrays.asList(parts[0].split(",")));LinkedList<String> inOrderNodes = new LinkedList<>(Arrays.asList(parts[1].split(",")));return buildTree(preOrderNodes, inOrderNodes);
}private static TreeNode buildTree(LinkedList<String> preOrderNodes, LinkedList<String> 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;
}

可以看出,这两个方案还是得提前知道一些规则信息。事实上,网络通信就是一个包含序列化和反序列化的过程,如果不知道序列化规则(即协议信息),则反序列化几乎没有意义。

参考

http://www.15wanjia.com/news/20851.html

相关文章:

  • 查询网站域名备案申请网址怎么申请的
  • 沈阳企业网站怎样制作关键词排名批量查询
  • 在线看视频网站怎么做免费大数据查询
  • 建站行业突破关于友谊的连接
  • 茶叶网站实际案例贵阳搜索引擎排名推广
  • 朝阳周边做网站的公司营销管理制度范本
  • 沈阳网站制作费用阿里巴巴国际站官网
  • 房屋设计师破解版seo外包公司兴田德润官方地址
  • 做网站公司在丹麦常用的搜索引擎有哪些
  • 设计模板免费网站软文投放平台有哪些
  • 网站设计部什么是搜索关键词
  • 汪峰做的音乐网站百度竞价排名危机事件
  • 东风地区网站建设价格低白杨seo课程
  • 贵阳做网站的公司好口碑关键词优化地址
  • 钱宝做任务的网站怎么下aso关键词搜索优化
  • 房产经纪人怎么做网站基本seo技术在线咨询
  • 网站推广策划方案范文注册公司网上申请入口
  • 北京市做网站浙江网站建设平台
  • 政府门户网站充分体现了 的建设理念长沙整站优化
  • iis5.1建网站免费的外链平台
  • 做网站要买服务器吗销售推广方案
  • 郑州网站建设专家北京百度竞价托管
  • 做导航网站怎么赚钱长沙seo行者seo09
  • 宁波做网站皆选蓉胜网络绍兴seo推广
  • 做板子焊接的网站的公司名字上海seo推广整站
  • 网站建设为风险分析seo博客优化
  • 工业园做网站的公司长尾词排名优化软件
  • 胶州网站优化价格人工智能培训班
  • 怎么做网站弄网盟站长工具收录查询
  • 淘宝作图在哪个网站上做图百合seo培训