题目 #

题目描述 #

现给定一棵二叉树的先序遍历序列和中序遍历序列，要求你计算该二叉树的高度。

输入描述 #

输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出描述 #

对于每组输入，输出一个整数，即该二叉树的高度。

输入示例 #

9 ABDFGHIEC FDHGIBEAC 7 Abcdefg gfedcbA

输出示例 #

5 7

解答 #

1 #

import java.io.*;
import java.util.*;
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    
}

public class Main{
    
    public static TreeNode getNode(char[] pre,char[] mid,int preStart,int preEnd,int midStart,int midEnd){
        if(midEnd==midStart){
            TreeNode temp= new TreeNode();
            temp.val=mid[midEnd];
            return temp;
        }
        char rootVal=pre[preStart];
        int midIndex=midStart;
        for(int i=midStart;i<=midEnd;i++){
            if(mid[i]==rootVal){
                midIndex=i;
                break;
            }
        }
        int leftLen=midIndex - midStart;
        int rightLen=midEnd - midStart - leftLen;
        TreeNode root=new TreeNode();
        root.val=rootVal;
        if(leftLen>0)
            root.left=getNode(pre,mid,preStart+1,preStart+leftLen,midStart,midIndex-1);
        if(rightLen>0)
            root.right=getNode(pre,mid,preStart+leftLen+1,preEnd,midIndex+1,midEnd);
    
        return root;
    }
    public static int getHeight(TreeNode root){
        if(root==null)return 0;
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        while((line=in.readLine())!=null){
            int num=Integer.parseInt(line);
            String pre=in.readLine();
            String mid=in.readLine();
            TreeNode root=Main.getNode(pre.toCharArray(),mid.toCharArray(),0,num-1,0,num-1);
            out.println(getHeight(root));
        }
        out.flush();
    }
}

主要的思路还是在于使用前序和中序进行构建二叉树需要注意的是构建过程中的边界条件识别：

        if(midEnd==midStart){
            TreeNode temp= new TreeNode();
            temp.val=mid[midEnd];
            return temp;
        }

也可以使用提供的API函数去实现

    private static TreeNode buildTree(String preOrder, String inOrder) {
        if (preOrder.isEmpty())
            return null;

        char rootVal = preOrder.charAt(0);
        TreeNode root = new TreeNode(rootVal);

        int rootIdx = inOrder.indexOf(rootVal);

        String leftPreOrder = preOrder.substring(1, rootIdx + 1);
        String leftInOrder = inOrder.substring(0, rootIdx);

        root.left = buildTree(leftPreOrder, leftInOrder);

        String rightPreOrder = preOrder.substring(rootIdx + 1);
        String rightInOrder = inOrder.substring(rootIdx + 1);

        root.right = buildTree(rightPreOrder, rightInOrder);

        return root;
    }

    private static int getHeight(TreeNode root) {
        if (root == null)
            return 0;

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.max(leftHeight, rightHeight) + 1;
    }

2 #

其实可以使用hash优化每一个中序的index情况在之后进行处理的时候就不需要再二次寻找mid中的index了

import java.io.*;
import java.util.*;
class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    
}

public class Main{
    
    public static TreeNode getNode(char[] pre,int preStart,int preEnd,int midStart,int midEnd , HashMap<Character,Integer> map){
        if(preStart==preEnd){
            TreeNode temp= new TreeNode();
            temp.val=pre[preEnd];
            return temp;
        }
        char rootVal=pre[preStart];
        int midIndex=map.get(rootVal);
        
        int leftLen=midIndex - midStart;
        int rightLen=midEnd - midStart - leftLen;
        TreeNode root=new TreeNode();
        root.val=rootVal;
        if(leftLen>0)
            root.left=getNode(pre,preStart+1,preStart+leftLen,midStart,midIndex-1,map);
        if(rightLen>0)
            root.right=getNode(pre,preStart+leftLen+1,preEnd,midIndex+1,midEnd,map);
    
        return root;
    }
    public static int getHeight(TreeNode root){
        if(root==null)return 0;
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
    public static HashMap<Character,Integer> map=new HashMap<>();
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        while((line=in.readLine())!=null){
            int num=Integer.parseInt(line);
            String pre=in.readLine();
            String mid=in.readLine();
            char[] midArray=mid.toCharArray();
            for(int i=0;i<num;i++){
                map.put(midArray[i],i);
            }
            TreeNode root=Main.getNode(pre.toCharArray(),0,num-1,0,num-1,map);
            out.println(getHeight(root));
        }
        out.flush();
    }
}

使用for填充map，然后进行map传递其中值得注意的点：

参数传递public static TreeNode getNode(char[] pre,int preStart,int preEnd,int midStart,int midEnd , HashMap<Character,Integer> map)要使用完整的map的类型 HashMap<Character,Integer> map，否则无法推断类型
在函数getNode中其实一直没需要使用mid这个中序信息，只需要index就够了，序列其实前序就够用