[编程题]二叉树后序遍历
import java.io.BufferedReader;
import java.io.InputStreamReader;import java.io.IOException;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s=br.readLine();//别忘了抛出异常
String[] ss=s.split(" ");
char[] pre=ss[0].toCharArray();
char[] in=ss[1].toCharArray();
postOrder(pre,0,pre.length-1,in,0,in.length-1);
}
public static TreeNode postOrder(char[] pre,int startPre,int endPre,char[] in,int startIn,int endIn){
if(startPre>endPre || startIn>endIn){
return null;
}
TreeNode root=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++){
if(in[i]==pre[startPre]){
root.left=postOrder(pre,startPre+1,i-startIn+startPre,in,startIn,i-1);//left
root.right=postOrder(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);//right
}
}
System.out.print(root.data);//输出，要放在后面，从里向外输出
return root;
}
}
class TreeNode{
TreeNode left;
TreeNode right;
char data;
public TreeNode(char data){
this.data=data;
}
}
发表于 2020-06-02 21:22:31
回复(0)
无需建树的Java实现
import java.util.Scanner;
/**
* @Author: coderjjp
* @Date: 2020-04-24 17:06
* @Description: 二叉树后序遍历
* @version: 1.0
*/
public class Main {
private static void getTree(String pre, int preL, int preR, String mid, int midL, int midR) {
if (preL>preR)
return ;
if (preL==preR){
System.out.print(pre.charAt(preL));
return;
}
for (int i=midL;i<=midR;i++){
if (pre.charAt(preL)==mid.charAt(i)){
getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
}
}
System.out.print(pre.charAt(preL));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String pre = sc.next();
String mid = sc.next();
getTree(pre,0,pre.length()-1,mid,0,mid.length()-1);
sc.close();
}
}
建树Java实现： import java.util.Scanner;
/**
* @Author: coderjjp
* @Date: 2020-04-24 17:06
* @Description: 二叉树后序遍历
* @version: 1.0
*/
public class Main {
private class TreeNode{
TreeNode left;
TreeNode right;
char val;
public TreeNode(char val) {
this.val = val;
}
}
public StringBuilder getLast(char[] pre,char[] mid){
TreeNode root = getTree(pre,0,pre.length-1,mid,0,mid.length-1);
StringBuilder sb = new StringBuilder();
lastSort(root,sb);
return sb;
}
private TreeNode getTree(char[] pre, int preL, int preR, char[] mid, int midL, int midR) {
if (preL>preR)
return null;
if (preL==preR)
return new TreeNode(pre[preL]);
TreeNode root = new TreeNode(pre[preL]);
for (int i=midL;i<=midR;i++){
if (pre[preL]==mid[i]){
root.left=getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
root.right=getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
}
}
return root;
}
private void lastSort(TreeNode root, StringBuilder sb) {
if (root==null)
return;
lastSort(root.left,sb);
lastSort(root.right,sb);
sb.append(root.val);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] pre = sc.next().toCharArray();
char[] mid = sc.next().toCharArray();
StringBuilder last = new Main().getLast(pre,mid);
System.out.println(last);
sc.close();
}
}
发表于 2020-04-24 18:08:10
回复(0)
import java.util.*;
class TreeNode{
char val;
TreeNode left;
TreeNode right;
TreeNode(char val){
this.val = val;
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
char[] pre = sc.next().toCharArray();
char[] in = sc.next().toCharArray();
TreeNode node = build(pre,in);
after(node);
}
public static TreeNode build(char[] pre,char[] in){
if(pre.length==0||in.length==0)
return null;
TreeNode node = new TreeNode(pre[0]);
for(int i =0;i<in.length;i++){
if(in[i]==pre[0]){
node.left=build(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
node.right=build(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
}
}
return node;
}
public static void after(TreeNode node){
if(node == null)
return;
after(node.left);
after(node.right);
System.out.print(node.val);
}
}
发表于 2020-02-29 16:06:31
回复(0)
先建树，后遍历输出：
import java.util.*;
class TreeNode{
char val;
TreeNode left = null;
TreeNode right = null;
TreeNode(char val) { this.val = val;}
}
public class Main{
public static void main(String []args){
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()){
String[] str = sc.nextLine().split(" ");
char []pre = str[0].toCharArray();
char []in = str[1].toCharArray();
TreeNode root = reCon(pre, in);
find(root);
}
}
public static TreeNode reCon(char[] pre, char[] in){
if (pre.length==0||in.length==0)
return null;
TreeNode root = new TreeNode(pre[0]);
for (int i=0;i<in.length;i++)
if (in[i]==pre[0]){
root.left = reCon(
Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
root.right = reCon(
Arrays.copyOfRange(pre,i+1,in.length),Arrays.copyOfRange(in,i+1,in.length));
}
return root;
}
//递归后序遍历方法：
public static void find(TreeNode root){
if (root == null) return;
find(root.left);
find(root.right);
System.out.print(root.val);
}
/* 非递归后序遍历方法：
public static void find(TreeNode root){
if (root == null) return;
TreeNode pCur = root;
TreeNode pLastVisit = null;
Stack<TreeNode> stack = new Stack<>();
while (pCur != null){
stack.push(pCur);
pCur = pCur.left;
}
while (!stack.isEmpty()){
pCur = stack.pop();
if (pCur.right == null||pLastVisit == pCur.right){
System.out.print(pCur.val);
pLastVisit = pCur;
}
else {
stack.push(pCur);
pCur = pCur.right;
while(pCur != null){
stack.push(pCur);
pCur = pCur.left;
}
}
}
}
*/
}
编辑于 2019-09-22 20:31:55
回复(0)
首先重建二叉树，然后，后序遍历输出
import java.util.Scanner;
//定义节点
class TreeNode{char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
//主函数
public class Main{
//递归重建二叉树
public static TreeNode beTree(char[] pre,int preStart,int preEnd,char[] in,int inStart,int inEnd){if(preStart>preEnd||inStart>inEnd){
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
for(int i = inStart;i<=inEnd;i++){
if(in[i]==pre[preStart]){
root.left = beTree(pre,preStart+1,i-inStart+preStart,in,inStart,i-1);
root.right = beTree(pre,i-inStart+preStart+1,preEnd,in,i+1,inEnd);
break;
}
}
return root;
}
//递归，后续遍历二叉树
public static void afterTree(TreeNode t){if(t!=null){
if(t.left!=null){
afterTree(t.left);
}
if(t.right!=null){
afterTree(t.right);
}
System.out.print(t.val);
}
}
//入口
public static void main(String[] args){Scanner scan = new Scanner(System.in);
char[] pre = scan.next().toCharArray();
char[] in = scan.next().toCharArray();
TreeNode t = beTree(pre,0,pre.length-1,in,0,in.length-1);
afterTree(t);
}
}
编辑于 2019-09-14 19:53:35
回复(0)
//重建二叉树，然后后序遍历二叉树就OK
import java.util.Scanner;
import javax.print.attribute.standard.PresentationDirection;
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) { val = x; }
}
public class Main {
public static String preStr;
public static String midStr;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int pos = s.indexOf(" ");
preStr = s.substring(0,pos);
midStr = s.substring(pos+1,s.length());
//System.out.println("pre:"+preStr);
//System.out.println("midS:"+midStr);
TreeNode rs = creat(preStr,0,preStr.length()-1,midStr,0,midStr.length()-1);
rView(rs);
}
public static void rView(TreeNode root){
if(root!=null){
rView(root.left);
rView(root.right);
System.out.print(root.val);
}
}
public static TreeNode creat(String preStr,int pstart,int pend,String midStr,int mstart,int mend){
if(mstart>mend||pstart>pend) return null;
char[] cmidStr= midStr.toCharArray();
char[] cpreStr=preStr.toCharArray();
TreeNode root = new TreeNode(cpreStr[pstart]);
for(int i = mstart;i<=mend;i++)
if(cmidStr[i]==cpreStr[pstart]){
int len = i-mstart;
root.left = creat(preStr,pstart+1,pstart+len,midStr,mstart,i-1);
root.right = creat(preStr,pstart+len+1,pend,midStr,i+1,mend);
}
return root;
}
}
发表于 2017-08-30 16:47:35
回复(0)
问题信息
通过挑战的用户
-
2023-02-21 17:58:53 -
2023-02-08 19:43:16 -
2022-09-15 15:33:35
-
2022-09-04 14:50:33
-
2022-08-14 15:38:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
