一、题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
题目：
有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。

输入：
每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果（每串只包含大写字母）。中间用单空格分隔。

输出：
输出仅一行，表示层序遍历的结果，结尾换行。

示例：
输入：
CBEFDA CBAEDF
输出：
ABDCEF

二、题解

  1. 先从后序和中序遍历字符串中构建树
  2. 按层遍历二叉树（广度搜索）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package org.stone.study.algo.ex202411;

import java.util.*;

public class TreeBuildAndTraverse {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // CBEFDA CBAEDF
        String[] arr = scanner.nextLine().split(" ");
        char[] postOrder = arr[0].toCharArray();
        char[] inOrder = arr[1].toCharArray();

        // 构建中序索引映射,不用每次都遍历 inOrder 数组
        Map<Character, Integer> inOrderMap = new HashMap<>();
        for (int i = 0; i < inOrder.length; i++) {
            inOrderMap.put(inOrder[i], i);
        }

        TreeNode root = buildTree(postOrder, 0, postOrder.length -1,  inOrder, 0,
                inOrder.length - 1,  inOrderMap);
        traverse(root);
    }

    /**
     * 从后序遍历和中序遍历构建二叉树
     * @param postOrder
     * @param postStart
     * @param postEnd
     * @param inOrder
     * @param inStart
     * @param inEnd
     * @param inOrderMap
     * @return
     */
    public static TreeNode buildTree(char[] postOrder, int postStart, int postEnd,
                                     char[] inOrder, int inStart, int inEnd, Map<Character, Integer> inOrderMap) {
        if (postOrder.length == 0 || inOrder.length == 0) {
            return null;
        }

        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        // 从后序遍历中确定根节点
        char rootVal = postOrder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        // 根节点在中序遍历中的位置
        int rootIndex = inOrderMap.get(rootVal);
        // 左子树的大小
        int leftSize = rootIndex - inStart;
        // 递归构建左子树和右子树
        root.setLeft(buildTree(postOrder, postStart, postStart + leftSize - 1, inOrder,
                inStart, inStart + leftSize - 1, inOrderMap));
        root.setRight(buildTree(postOrder, postStart + leftSize, postEnd - 1,  inOrder,
                rootIndex + 1, inEnd, inOrderMap));

        return root;
    }

    /**
     * 层序遍历二叉树
     * @param root
     */
    public static void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.getVal() + " ");

            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }
            if(node.getRight() != null) {
                queue.offer(node.getRight());
            }
        }
    }
}


/**
 * 二叉树节点
 */
class TreeNode {
    private char val;
    private TreeNode left;
    private TreeNode right;

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

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

    public char getVal() {
        return val;
    }

    public void setVal(char val) {
        this.val = val;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}