笔试题-构建非二叉树，且非递归遍历-利用栈

news/2024/10/19 23:47:53/

普通版本

java">package com.fang.恒天软件;import java.util.*;
import java.util.stream.Stream;public class Tree {TreeNode head;public Tree(TreeNode node) {this.head = node;}class ForeachNoMethodException extends Exception {public ForeachNoMethodException(String message) {super(message);}}private static final String EXCEPTION_MSG = "没有该遍历方式，请从【1(深度优先前序遍历所有)、2(深度优先前序遍历奇数)、3(深度优先前序遍历偶数)、" +"4(深度优先后序遍历所有)、5(深度优先后序遍历奇数)、6(深度优先后序遍历偶数)】";/*** 默认不传走顺序遍历*/public void foreach() {foreach(ForEachMethod.orderFrontMethod);}public void foreach(ForEachMethod method) {try {if (Stream.of("1", "2", "3").anyMatch(val -> val.equals(method.value))) {print(foreachFront(method));;} else if (Stream.of("4", "5", "6").anyMatch(val -> val.equals(method.value))) {print(foreachBack(method));} else {throw new ForeachNoMethodException(EXCEPTION_MSG);}} catch (ForeachNoMethodException ignored) {}}private void print(List<Integer> list) {list.forEach(val -> {if (list.indexOf(val) == list.size() - 1) {System.out.print(val);} else {System.out.print(val + " ");}});}/*** 前序遍历*/private List<Integer> foreachFront(ForEachMethod method) {List<Integer> result = new ArrayList<>();if (Objects.isNull(head)) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.empty()) {TreeNode node = stack.pop();if (Objects.equals(method, ForEachMethod.orderFrontMethod)) {result.add(node.value);} else if (Objects.equals(method, ForEachMethod.oddFrontMethod) && node.value % 2 != 0) {result.add(node.value);} else if (Objects.equals(method, ForEachMethod.evenFrontMethod) && node.value % 2 == 0) {result.add(node.value);}for (int i = node.nodes.size() - 1; i >= 0; i--) {stack.push(node.nodes.get(i));}}return result;}/*** 后序遍历*/private List<Integer> foreachBack(ForEachMethod method) {List<Integer> result = new ArrayList<>();if (Objects.isNull(head)) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.isEmpty()) {TreeNode cur = stack.pop();if (Objects.equals(method, ForEachMethod.orderBackMethod)) {result.add(cur.value);} else if (Objects.equals(method, ForEachMethod.oddBackMethod) && cur.value % 2 != 0) {result.add(cur.value);} else if (Objects.equals(method, ForEachMethod.evenBackMethod) && cur.value % 2 == 0) {result.add(cur.value);}for (TreeNode node : cur.nodes) {stack.push(node);}}Collections.reverse(result);return result;}/*** 非二叉树的节点*/static class TreeNode {Integer value;List<TreeNode> nodes;public TreeNode(Integer value, List<TreeNode> nodes) {this.value = value;this.nodes = nodes;}public TreeNode(Integer value) {this.value = value;this.nodes = new ArrayList<>();}}/*** 打印节点方式*/enum ForEachMethod {// 根 -> 左 -> 右orderFrontMethod("1", "深度优先前序遍历所有"),oddFrontMethod("2", "深度优先前序遍历奇数"),evenFrontMethod("3", "深度优先前序遍历偶数"),// 左 右 根orderBackMethod("4", "深度优先后序遍历所有"),oddBackMethod("5", "深度优先后序遍历奇数"),evenBackMethod("6", "深度优先后序遍历偶数");final String value;final String name;ForEachMethod(String value, String name) {this.value = value;this.name = name;}}}class Demo {public static void main(String[] args)  {List<Tree.TreeNode> treeNodes = new ArrayList<>();/***              1*           /  |  \*        2     3      4*      / | \  / \    / \*     5  6 7 8   9  10  11*/Tree.TreeNode node5 = new Tree.TreeNode(5);Tree.TreeNode node6 = new Tree.TreeNode(6);Tree.TreeNode node7 = new Tree.TreeNode(7);Tree.TreeNode node2 = new Tree.TreeNode(2, Arrays.asList(node5, node6, node7));Tree.TreeNode node8 = new Tree.TreeNode(8);Tree.TreeNode node9 = new Tree.TreeNode(9);Tree.TreeNode node3 = new Tree.TreeNode(3, Arrays.asList(node8, node9));Tree.TreeNode node10 = new Tree.TreeNode(10);Tree.TreeNode node11 = new Tree.TreeNode(11);Tree.TreeNode node4 = new Tree.TreeNode(4, Arrays.asList(node10, node11));Tree.TreeNode head = new Tree.TreeNode(1, Arrays.asList(node2, node3, node4));Tree tree = new Tree(head);tree.foreach(Tree.ForEachMethod.orderFrontMethod); // 1 2 5 6 7 3 8 9 4 10 11System.out.println();tree.foreach(Tree.ForEachMethod.oddFrontMethod); // 1 5 7 3 9 11System.out.println();tree.foreach(Tree.ForEachMethod.evenFrontMethod); // 2 6 8 4 10System.out.println("\n-----------------------------------------");tree.foreach(Tree.ForEachMethod.orderBackMethod); // 5 6 7 2 8 9 3 10 11 4 1System.out.println();tree.foreach(Tree.ForEachMethod.oddBackMethod); // 5 7 9 3 11 1System.out.println();tree.foreach(Tree.ForEachMethod.evenBackMethod); // 6 2 8 10 4}
}

使用策略模式

java">package com.fang.恒天软件;import java.util.*;public class Tree {TreeNode head;public Tree(TreeNode node) {this.head = node;}class ForeachNoMethodException extends Exception {public ForeachNoMethodException(String message) {super(message);}}private static final String EXCEPTION_MSG = "没有该遍历方式，请从【1(深度优先前序遍历所有)、2(深度优先前序遍历奇数)、3(深度优先前序遍历偶数)、" +"4(深度优先后序遍历所有)、5(深度优先后序遍历奇数)、6(深度优先后序遍历偶数)】";/*** 默认不传走顺序遍历*/public void foreach() {foreach(ForEachMethod.orderFrontMethod);}private void print(List<Integer> list) {list.forEach(val -> {if (list.indexOf(val) == list.size() - 1) {System.out.print(val);} else {System.out.print(val + " ");}});}public void foreach(ForEachMethod method) {ForEachFactory factory = new ForEachFactory();print(factory.getForEachWay(method).execute());}class ForEachFactory {Map<Tree.ForEachMethod, Tree.ForEachWay> forEachWayMap = new HashMap<>(16, 0.75F);public ForEachFactory() {registerForEachWay(ForEachMethod.orderFrontMethod, new FrontForEach(ForEachMethod.orderFrontMethod));registerForEachWay(ForEachMethod.oddFrontMethod, new FrontForEach(ForEachMethod.oddFrontMethod));registerForEachWay(ForEachMethod.evenFrontMethod, new FrontForEach(ForEachMethod.evenFrontMethod));registerForEachWay(ForEachMethod.orderBackMethod, new BackForEach(ForEachMethod.orderBackMethod));registerForEachWay(ForEachMethod.oddBackMethod, new BackForEach(ForEachMethod.oddBackMethod));registerForEachWay(ForEachMethod.evenBackMethod, new BackForEach(ForEachMethod.evenBackMethod));}private void registerForEachWay(Tree.ForEachMethod method, Tree.ForEachWay way) {forEachWayMap.put(method, way);}public Tree.ForEachWay getForEachWay(ForEachMethod method)  {try {if (forEachWayMap.containsKey(method)) {return forEachWayMap.get(method);} else {throw new ForeachNoMethodException(EXCEPTION_MSG);}} catch (ForeachNoMethodException e) {}return null;}}interface ForEachWay {List<Integer> execute();}class FrontForEach implements ForEachWay {ForEachMethod method;public FrontForEach(ForEachMethod method) {this.method = method;}@Overridepublic List<Integer> execute() {List<Integer> result = new ArrayList<>();if (Objects.isNull(head)) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.empty()) {TreeNode node = stack.pop();if (Objects.equals(method, ForEachMethod.orderFrontMethod)) {result.add(node.value);} else if (Objects.equals(method, ForEachMethod.oddFrontMethod) && node.value % 2 != 0) {result.add(node.value);} else if (Objects.equals(method, ForEachMethod.evenFrontMethod) && node.value % 2 == 0) {result.add(node.value);}for (int i = node.nodes.size() - 1; i >= 0; i--) {stack.push(node.nodes.get(i));}}return result;}}class BackForEach implements ForEachWay {ForEachMethod method;public BackForEach(ForEachMethod method) {this.method = method;}@Overridepublic List<Integer> execute() {List<Integer> result = new ArrayList<>();if (Objects.isNull(head)) {return result;}Stack<TreeNode> stack = new Stack<>();stack.push(head);while (!stack.isEmpty()) {TreeNode cur = stack.pop();if (Objects.equals(method, ForEachMethod.orderBackMethod)) {result.add(cur.value);} else if (Objects.equals(method, ForEachMethod.oddBackMethod) && cur.value % 2 != 0) {result.add(cur.value);} else if (Objects.equals(method, ForEachMethod.evenBackMethod) && cur.value % 2 == 0) {result.add(cur.value);}for (TreeNode node : cur.nodes) {stack.push(node);}}Collections.reverse(result);return result;}}/*** 非二叉树的节点*/static class TreeNode {Integer value;List<TreeNode> nodes;public TreeNode(Integer value, List<TreeNode> nodes) {this.value = value;this.nodes = nodes;}public TreeNode(Integer value) {this.value = value;this.nodes = new ArrayList<>();}}/*** 打印节点方式*/enum ForEachMethod {// 根 -> 左 -> 右orderFrontMethod("1", "深度优先前序遍历所有"),oddFrontMethod("2", "深度优先前序遍历奇数"),evenFrontMethod("3", "深度优先前序遍历偶数"),// 左 右 根orderBackMethod("4", "深度优先后序遍历所有"),oddBackMethod("5", "深度优先后序遍历奇数"),evenBackMethod("6", "深度优先后序遍历偶数");final String value;final String name;ForEachMethod(String value, String name) {this.value = value;this.name = name;}}}class Demo {public static void main(String[] args)  {List<Tree.TreeNode> treeNodes = new ArrayList<>();/***              1*           /  |  \*        2     3      4*      / | \  / \    / \*     5  6 7 8   9  10  11*/Tree.TreeNode node5 = new Tree.TreeNode(5);Tree.TreeNode node6 = new Tree.TreeNode(6);Tree.TreeNode node7 = new Tree.TreeNode(7);Tree.TreeNode node2 = new Tree.TreeNode(2, Arrays.asList(node5, node6, node7));Tree.TreeNode node8 = new Tree.TreeNode(8);Tree.TreeNode node9 = new Tree.TreeNode(9);Tree.TreeNode node3 = new Tree.TreeNode(3, Arrays.asList(node8, node9));Tree.TreeNode node10 = new Tree.TreeNode(10);Tree.TreeNode node11 = new Tree.TreeNode(11);Tree.TreeNode node4 = new Tree.TreeNode(4, Arrays.asList(node10, node11));Tree.TreeNode head = new Tree.TreeNode(1, Arrays.asList(node2, node3, node4));Tree tree = new Tree(head);tree.foreach(Tree.ForEachMethod.orderFrontMethod); // 1 2 5 6 7 3 8 9 4 10 11System.out.println();tree.foreach(Tree.ForEachMethod.oddFrontMethod); // 1 5 7 3 9 11System.out.println();tree.foreach(Tree.ForEachMethod.evenFrontMethod); // 2 6 8 4 10System.out.println("\n-----------------------------------------");tree.foreach(Tree.ForEachMethod.orderBackMethod); // 5 6 7 2 8 9 3 10 11 4 1System.out.println();tree.foreach(Tree.ForEachMethod.oddBackMethod); // 5 7 9 3 11 1System.out.println();tree.foreach(Tree.ForEachMethod.evenBackMethod); // 6 2 8 10 4}
}

http://www.ppmy.cn/news/1443313.html

相关文章

go是如何运行的？

go是如何运行的？

前言 go程序的入口是main函数吗&#xff1f;诚然很多程序的入口都是main,比如java,C,C等&#xff0c;但是go由于他的运行时环境是代码&#xff0c;而不是像Java那样有自己的虚拟机&#xff0c;所以程序在运行main函数之前&#xff0c;需要做很多的准备工作&#xff0c; 该文章…
阅读更多...
(超全)python图像处理详细解析（4）

(超全)python图像处理详细解析（4）

图像处理 34.边缘检测35.gabor滤波36.画线条37.画实心圆38.画四边形39.画六边形40.画椭圆形41.画空心圆42.平移图像43.图像的镜像 34.边缘检测 &#xff08;1&#xff09;sobel算子&#xff1a;可用来检测边缘 &#xff08;2&#xff09;scharr算子&#xff1a;同sobel算子 &a…
阅读更多...
python的json序列化和反序列化

python的json序列化和反序列化

在Python中解析JSON数据非常简单&#xff0c;你可以使用内置的json模块。这个模块提供了loads()函数来解析JSON字符串&#xff0c;以及load()函数来解析JSON文件。 import json# JSON字符串 json_str {"name": "John", "age": 30, "city&…
阅读更多...
八十八张表截图

八十八张表截图

88表截图&#xff1a;
阅读更多...
数字孪生智慧水务监测管理平台

数字孪生智慧水务监测管理平台

1、行业背景 水务局管理数据量多&#xff0c;且视频、传感器等数据分散在不同系统中&#xff0c;在获取到水文监控点的数据后&#xff0c;需花费大量人力及时间去查看识别等&#xff0c;投入成本高&#xff0c;且难以结合业务场景发挥出应有价值。 2、解决方案 数字孪生智慧…
阅读更多...
企业计算机服务器中了rmallox勒索病毒怎么办，rmallox勒索病毒解密流程

企业计算机服务器中了rmallox勒索病毒怎么办，rmallox勒索病毒解密流程

对于众多的企业来说&#xff0c;通过网络开展各项工作业务已经成为常态&#xff0c;网络为企业的生产运营提供了极大便利&#xff0c;也大大加快了企业发展的步伐&#xff0c;但众多企业越来越重视企业发展中的核心数据安全问题。近期&#xff0c;云天数据恢复中心接到众多企业…
阅读更多...
用Python编写一个简单的数字累加器 数字累加器

用Python编写一个简单的数字累加器 数字累加器

目录 一.总体说明 二.完整代码 三.逐行分析 一.总体说明 数字累加器是一种用于对数字进行持续累加的设备或算法。它可以在每次输入一个数字时将其与之前的累加结果相加，并更新累加结果。数字累加器通常用于计算总和、平均值或其他需要对连续数字进行累加的应用场景。 在计…
阅读更多...
区块链交易所技术开发架构解析 交易所开发团队

区块链交易所技术开发架构解析 交易所开发团队

区块链交易所是加密货币市场中的关键基础设施之一&#xff0c;它提供了一个平台&#xff0c;让用户可以买卖各种数字资产。而搭建一个功能完善、安全可靠的交易所需要一个复杂的技术开发架构&#xff0c;以及一个协调配合的交易所开发团队。下面我们将分析交易所的技术架构以及…
阅读更多...
最新文章

Copyright @ 2022~2023