已知前序，中序，输出后序。最长回文问题

朋友们，好久不见了。最近忙着其他事情，一直没有到博客园转转。你们还好吗？

已知二叉树的前序和中序，输出后序。不能用其他非标准库

输入：AB

输出：BA

AB
BA

 1 import java.util.Scanner;
 2 /**
 3  * 数据结构
 4  * @author xiaoyi115
 5  * @webSite http://www.cnblogs.com/xiaoyi115/
 6  * @email liangliang.mao@foxmail.com
 7  * @param <DataType>
 8  */
 9 class Node{
10     public String nodeValue;
11     public Node leftNode;
12     public Node rightNode;
13     public Node(){
14         leftNode=null;
15         rightNode=null;
16     }
17     
18 }
19 public class Main {
20     public static void getTree(Node root,String pre,String mid){
21         if (pre.length()<=0) {
22             return;
23         }
24         if (root==null) {
25             root=new Node();
26         }
27         String value=String.valueOf(pre.charAt(0));
28         root.nodeValue=value;
29         int i=0;
30         String midvalue=String.valueOf(mid.charAt(i));
31         while(i<mid.length()&&!value.equals(midvalue)){
32             i++;
33             midvalue=String.valueOf(mid.charAt(i));
34         }
35         if(i>=1&&i<=pre.length()){
36             root.leftNode=new Node();
37             getTree(root.leftNode,pre.subSequence(1, i+1).toString(), mid.subSequence(0, i).toString());
38         }
39         if (i<pre.length()-1) {
40             root.rightNode=new Node();
41             getTree(root.rightNode, pre.subSequence(i+1, pre.length()).toString(), mid.subSequence(i+1, mid.length()).toString());
42         }
43     }
44     public static void print(Node root){
45         if(root==null)
46             return;
47         print(root.leftNode);
48         print(root.rightNode);
49         System.out.print(root.nodeValue);
50     }
51     public static void main(String[] args){
52         Scanner scanner=new Scanner(System.in);
53         
54         String pre=scanner.next();
55         String mid=scanner.next();
56         
57         Node root=new Node();
58         getTree(root, pre, mid);
59         print(root);
60     }
61 }

最长回文。比如：

3
abababa
aaaabaa
acacdas
输出：
7
5
3
1、暴力解法。O(N3)
2、动态规划。O(N2)
3、还有一种很牛逼的方法，是O(N).我对这个算法还是不明觉厉中。

 1 int times=scanner.nextInt();
 2         //x:
 3         for (int N = 0; N < times; N++) {
 4             if(scanner.hasNext()){
 5                 char[] str=scanner.next().toCharArray();
 6                 int maxLen=1;
 7                 int[][] A=new int[str.length][str.length];
 8                 for (int i = 0; i < str.length; i++) {
 9                     for (int j = 0; j < str.length; j++) {
10                         if (i==j) {
11                             A[i][j]=1;
12                         }else {
13                             A[i][j]=0;
14                         }
15                     }
16                 }
17                 
18                 for (int len = 2; len <=str.length; len++) {//表示长度
19                     for (int begin = 0; begin < str.length-len+1; begin++) {
20                         if((str[begin]==str[begin+len-1]&&len==2)||(str[begin]==str[begin+len-1]&&A[begin+1][begin+len-2]==1)){
21                             maxLen=len;
22                             A[begin][begin+len-1]=1;
23                         }
24                     }
25                 }
26                 System.out.println(maxLen);
27                 }
28             }