21. 构造二叉树

时间限制：1.000S 空间限制：32MB

题目描述

给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入描述

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出描述

对于每组输入，输出对应的二叉树的后续遍历结果。

输入示例

DBACEGF ABCDEFG

BCAD CBAD

输出示例

ACBFGED

CDAB

解法一(递归+hash)

思路分析:

1. 手动构建二叉树节点
2. 通过递归的方式 按后序遍历输出二叉树
3. 通过哈希的方式缓存记录中序遍历字符的索引;并通过递归的方式构造二叉树

实现代码如下:

public class k_21_ConstructBinaryTree {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String pre = in.next();
            String inOrder = in.next();
            Map<Character, Integer> inMap = new HashMap<>();
            int preLen = pre.length();
            int inLen = inOrder.length();
            for (int i = 0; i < inLen; ++ i) {
                inMap.put(inOrder.charAt(i), i);
            }
            TreeNode root = buildTree(pre, 0, preLen-1, inMap, 0, inLen-1);
            postOrderTraversal(root);
            System.out.println();
        }
    }
    private static TreeNode buildTree(String pre, int preStart, int preEnd, Map<Character, Integer> inMap, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        // 根据前序遍历获取根节点
        char val = pre.charAt(preStart);
        TreeNode root = new TreeNode(val);
        // 获取左右子树区间
        Integer index = inMap.get(val);
        root.left = buildTree(pre, preStart+1, index-inStart+preStart, inMap, inStart, index-1);
        root.right = buildTree(pre, index-inStart+preStart+1, preEnd, inMap, index+1, inEnd);
        return root;
    }
    // 二叉树后序遍历
    private static void postOrderTraversal(TreeNode root) {
        // 后序遍历 左右中
        if (root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val);
    }
    public static class TreeNode {
        char val;
        TreeNode right;
        TreeNode left;

        public TreeNode() {
        }

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

运行结果如下:

运行时间： 356ms 消耗内存： 12812kb

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$