构造二叉树并输出层次遍历序列

题目

给定两个字符串,分别是二叉树的后序遍历和中序遍历,打印二叉树的层次遍历序列.

思路

• 构造出二叉树,然后层次遍历
• 其实就是完全糅合二叉树构造和层次遍历两道题目
• leetcode 106. 从中序与后序遍历序列构造二叉树
• leecode 102. 二叉树的层序遍历

代码

import java.util.*;

public class Main3 {
    
    private static Map<Character, Integer> inOrderChar2Index;


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String baOrder = in.next();
        String inOrder = in.next();

        char[] baOrderArray = baOrder.toCharArray();
        char[] inOrderArray = inOrder.toCharArray();

        initInOrderChar2Index(inOrderArray);

        TreeNode tree = buildTree(baOrderArray, 0, baOrderArray.length - 1,
                inOrderArray, 0, inOrderArray.length - 1);


        StringBuilder result = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(tree);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node == null){
                continue;
            }
            result.append(node.val);
            queue.offer(node.left);
            queue.offer(node.right);
        }

        System.out.println(result.toString());
    }

    private static void initInOrderChar2Index(char[] inOrderArray) {
        inOrderChar2Index = new HashMap<>();
        for (int i = 0; i < inOrderArray.length; i++) {
            inOrderChar2Index.put(inOrderArray[i], i);
        }
    }

    private static TreeNode buildTree(char[] baOrderArray, int baStart, int baEnd, 
                                      char[] inOrderArray, int inStart, int inEnd) {
        if (baStart > baEnd){
            return null;
        }

        TreeNode treeNode = new TreeNode(baOrderArray[baEnd]);;

        Integer inOrderIndex = inOrderChar2Index.get(baOrderArray[baEnd]);

        int leftTreeLength = inOrderIndex - inStart;

        treeNode.left = buildTree(baOrderArray, baStart, baStart + leftTreeLength - 1,
                inOrderArray, inStart, inOrderIndex - 1);

        treeNode.right = buildTree(baOrderArray, baStart + leftTreeLength, baEnd - 1,
                inOrderArray, inOrderIndex + 1, inEnd);

        return treeNode;
    }
}

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}