华为OD机试真题新系统 Java实现【输出二叉树后序遍历结果】

输出二叉树后序遍历结果更多语言题解可查看华为OD机试新系统真题 - 输出二叉树后序遍历结果(C/C/Py/Java/Js/Go)题解题目内容给定二叉树前序遍历和中序遍历的字符串以及需要删除的节点要求先解析这两个字符串获取对应二叉树再做删除指定节点操作然后输出该二叉树的后序遍历结果。删除节点规则指定节点是根节点则不做删除操作指定节点是叶子节点则直接删除指定节点是内部节点如果是左子节点则把该节点的左子树挂接到它的父节点然后删除该节点以及它的右子树如果是右子节点则把该节点的右子树挂接到它的父节点然后删除该节点以及它的左子树。输入描述s t r i n g stringstringp r e o r d e r S t r preorderStrpreorderStr// 前序遍历字符串s t r i n g stringstringi n o r d e r S t r inorderStrinorderStr// 中序遍历字符串c h a r charcharb e D e l e t e d N o d e beDeletedNodebeDeletedNode// 待删除的节点输出描述s t r i n g stringstringo u t p u t S t r outputStroutputStr// 返回 “” 或者 后序遍历的字符串补充说明给定的p r e o r d e r S t r preorderStrpreorderStr和i n o r d e r S t r inorderStrinorderStr是由大写字母组成的字符串长度为2 22~26 2626每个字母表示一个节点值且节点值唯一给定的b e D e l e t e d L e a f N o d e beDeletedLeafNodebeDeletedLeafNode是一个大写字母如果输入的不是大写字母、或者找不到对应节点、或者找到的节点是根节点都不做删除操作如果做了删除操作则输出删除叶子节点后的二叉树后序遍历结果否则直接输出二叉树后序遍历结p r e o r d e r S t r preorderStrpreorderStr和i n o r d e r S t r inorderStrinorderStr符合如下场景则输出空串例如字符串中存在非大写字母长度超出范围节点值不唯一两个字符串长度不一致两个字符串元素不相同无法解析出对应二叉树。样例1输入23a ABC A输出说明输入存在非法字符串样例2输入ADE DAE E输出DA样例3输入AABCD BAACD A输出说明出现重复节点值样例4输入ABC BAC A输出BCA说明找到的节点A AA是根节点样例5输入ABCDE BAHDE E输出说明输入的两个遍历结果元素不相同题解思路思路二叉树首先判断以下几个非法情况存在非法情况直接返回空字符串:前序遍历和后序遍历长度是否不一致前序遍历或后序遍历长度是否超过限制判断前序遍历和后序遍历是否包含重复字符或者非大写字母以及元素是否不同。利用前序遍历和后序遍历结果还原二叉树前序遍历的顺序为父节点-左子-右子中序遍历顺序为左子-父节点-右子,简单说说还原逻辑以ABDECFH和DBEAFCH为例根据前序遍历规律,可以得出第一个值是父节点的值A。在中序遍历种找到对应的父节点的值所处位置j 3 根据中序遍历规律此时可知DBE为左子树中序遍历结果FCH为右子树中序遍历结果。根据中序遍历得知左右子树长度之后同时也可知道左子树前序遍历结果为BDE右子树前序遍历结果为CFH按照上述123的规律使用递归即可还原出二叉树。2为正确遍历结果还原结果的方法无法构建二叉树可在二叉树递归还原进行判断例如前序和中序节点不一致无法在中序遍历结果中找到父节点。发生上面情况时标记为非法并直接终止构建即可。删除节点比较简单题目要求不会删除根节点如果根节点等于要删除节点不进行处理。接下来进行递归删除处理逻辑如下当前节点为current如果current-left ! null, 并且root-left-value beDeletedNode,将左子的左子树挂载到当前节点的左子树位置即可。如果current-root ! null, 并且root-right-value beDeletedNode,将右子节点的右子树挂载到当前节点的右子树位置即可。接下来递归生成当前二叉树的后序遍历结果即可。这部分很简单可参照下面代码。往期真题通过中序、后序遍历还原二叉树感兴趣的看看:华为OD机试真题-二叉树的广度优先遍历codeimportjava.io.*;importjava.util.*;publicclassMain{staticclassNode{Nodeleft;Noderight;charvalue;Node(){}Node(charvalue){this.valuevalue;}}staticbooleanvalidtrue;// 通过前序和中序还原二叉树staticNodegenerateNode(Stringpreorder,StringinOrder){if(preorder.isEmpty()){returnnull;}if(preorder.length()!inOrder.length()){validfalse;returnnull;}intnpreorder.length();NoderootnewNode(preorder.charAt(0));// 确定左子树的长度intj0;for(;jn;j){if(preorder.charAt(0)inOrder.charAt(j)){break;}}// 指定节点找不到if(jn){validfalse;returnnull;}// 确定左右子树中序遍历结果StringinOrderLeftinOrder.substring(0,j);StringinOrderRightinOrder.substring(j1);// 确定左右子树前序遍历结果StringpreorderLeftpreorder.substring(1,j1);StringpreorderRightpreorder.substring(j1);if(!inOrderLeft.isEmpty()){root.leftgenerateNode(preorderLeft,inOrderLeft);}if(!inOrderRight.isEmpty()){root.rightgenerateNode(preorderRight,inOrderRight);}returnroot;}// 递归获取后序遍历结果staticStringdfs(Noderoot){if(rootnull){return;}Stringres;resdfs(root.left);resdfs(root.right);resroot.value;returnres;}// 统计每个大写字母数量并判断是否包含除大写字母之外其它字符staticbooleancountChar(int[]count,Stringstr){for(charc:str.toCharArray()){if(cZcA){count[c-A];}else{returnfalse;}}returntrue;}// 移除指定节点staticvoidremoveNode(Noderoot,charc){if(rootnull){return;}if(root.left!null){// 移除if(root.left.valuec){root.leftroot.left.left;return;}// 递归向下removeNode(root.left,c);}if(root.right!null){// 移除if(root.right.valuec){root.rightroot.right.right;return;}// 递归向下removeNode(root.right,c);}}staticStringdeleteTreeNode(StringpreorderStr,StringinorderStr,charbeDeletedNode){// 判断非法情况// 长度不一致if(preorderStr.length()!inorderStr.length()){return;}// 长度超过限制if(preorderStr.length()26||preorderStr.length()2){return;}int[]countAnewint[26],countBnewint[26];booleanflagcountChar(countA,preorderStr);// 包含非大写字符if(!flag){return;}flagcountChar(countB,inorderStr);if(!flag){return;}// 判断是否存在重复元素以及两个字符串元素是否相同for(inti0;i26;i){if(countA[i]!countB[i]){return;}if(countA[i]1){return;}}// 构造出对应二叉树NoderootgenerateNode(preorderStr,inorderStr);// 无法构造出对应二叉树if(!valid){return;}// 未root情况才需要进行移除if(!(root.valuebeDeletedNode)){removeNode(root,beDeletedNode);}// 获取对应后序遍历结果Stringresdfs(root);returnres;}// 作者 csdn无限码力publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringpreorderStrbr.readLine();StringinorderStrbr.readLine();charbeDeletedNodebr.readLine().charAt(0);System.out.print(deleteTreeNode(preorderStr,inorderStr,beDeletedNode));}}