首页 > 代码库 > hihoCoder 1049 后序遍历 最详细的解题报告
hihoCoder 1049 后序遍历 最详细的解题报告
题目来源:后序遍历
解题思路:开始时我只知道先通过先序、中序求出二叉树,然后再后序遍历二叉树,这当然也是一种解题思路,但是会做一些无用功,比如:计算二叉树。其实,可以直接通过先序序列和中序序列直接求出后序序列的。思路如下:
1、取先序序列的第一个节点为根节点;
2、在中序序列中找到根节点的下标,将中序序列分成left和right两部分;
3、根据left和right的长度计算出先序序列中的根节点的左右孩子;
4、依次递归计算出左孩子,右孩子,返回 左孩子+右孩子+根节点。
具体算法(Java版,直接AC)
1 import java.util.Scanner; 2 3 public class Main { 4 5 public static String post_order(String preOrder,String inOrder){ 6 if(preOrder.length()>0&&preOrder.length()==inOrder.length()){ 7 char root=preOrder.charAt(0); //获取根节点 8 int index=inOrder.indexOf(root); //在中序序列中找出根节点的下标 9 if(index!=-1){10 String left=inOrder.substring(0, index);//中序序列中左孩子串11 String right=inOrder.substring(index+1);//中序序列中右孩子串12 //递归计算并返回计算后的左孩子+右孩子+根节点13 return post_order(preOrder.substring(1, left.length()+1),left)
+post_order(preOrder.substring(left.length()+1),right)
+root;14 }15 }16 return "";17 }18 19 public static void main(String[] args) {20 Scanner scanner=new Scanner(System.in);21 System.out.println(post_order(scanner.next(),scanner.next()));22 }23 }
hihoCoder 1049 后序遍历 最详细的解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。