一、题目内容

二、题解

解法1：

思路

二叉树重建 + 二叉树层序遍历变形

代码

public class Solution {
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = rebuild(xianxu,zhongxu);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<Integer> ansList = new ArrayList<>();
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i<size;i++){
                TreeNode node = queue.poll();
                if(i == size-1){
                    ansList.add(node.val);
                }
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        int[] res = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            res[i] = ansList.get(i);
        }
        return res;
    }
    private TreeNode rebuild(int[] preorder,int[] inorder){
        //递归调用的终止条件
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int i;
        for(i = 0;i<inorder.length;i++){
            if(root.val == inorder[i]){
                root.left = rebuild(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
                root.right = rebuild(Arrays.copyOfRange(preorder,i+1,inorder.length),Arrays.copyOfRange(inorder,i + 1, inorder.length));
                break;
            }
        }
        return root;
    }
}