前言：参加公司技术考试，时间90分钟，包括20多道逻辑推理题和20多道计算机考研四门课的题后，还有最后一道编程题：输入节点个数和节点各个值，输出根据各节点值形成的二叉搜索树的最后两层的节点序列。当时时间不够没做出来，中午抽空做了下。
解题思路：首先是建树，我的办法是在搜索时把各个值插入到相应位置，并记录各个节点所在的层数，建好后根据层数比较输出序列。
代码如下：

package com.get.recursive.service;
import org.springframework.stereotype.Service;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Node {
    int data;
    int layer;
    Node leftNode;
    Node rightNode;
}
/**
 * @author yml
 * @date 2020/6/11
 * @description
 */
@Service
public class Tree {
    private static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        System.out.println("tree");
        Scanner scanner = new Scanner(System.in);
        List<Integer> abc = new ArrayList<>();
        int a = scanner.nextInt();
        for (int i=0;i<a; i++) {
            abc.add(scanner.nextInt());
        }
        treeMethod(abc);
    }

    /**
     * 二叉搜索树算法调用
     * @param abc
     */
    private static void treeMethod(List<Integer> abc){

        Node root = new Node();
        root.data = abc.get(0);
        root.layer = 0;
        int maxLayer = 0;
        for (int i = 1; i < abc.size(); i ++) {
            Node r = new Node();
            r.data = abc.get(i);
            int currentLayer = search(root,r);//获取二叉树最大层数
            maxLayer = maxLayer<currentLayer?currentLayer:maxLayer;
        }
        preOrder(root,maxLayer);
        System.out.println(list);
    }

    /**
     * 先序遍历，输出为有序数列
     * @param root
     * @param maxLayer
     */
    private static void preOrder(Node root, int maxLayer) {
        if (root.leftNode != null) {
            preOrder(root.leftNode,maxLayer);
        }
        if (root.layer >= maxLayer-1) {
            list.add(root.data);
        }
        System.out.println("data:"+root.data+"   layer:" +root.layer);
        if (root.rightNode != null) {
            preOrder(root.rightNode, maxLayer);
        }
    }

    /**
     *
     * @param root 根节点
     * @param node 待插入节点，存在则不插入
     * @return
     */
    private static int search(Node root, Node node) {
        Node r = root;
        if (root == null) return -1;
        if (root.data == node.data) return 0;
        while (r != null) {
            if (node.data>r.data) {
                if (r.rightNode == null) {
                    node.layer = r.layer+1;
                    r.rightNode = node;
                    return node.layer;
                }
                r=r.rightNode;
            } else if (node.data<r.data) {
                if (r.leftNode == null) {
                    node.layer = r.layer+1;
                    r.leftNode = node;
                    return node.layer;
                }
                r=r.leftNode;
            } else {
                return root.layer;
            }
        }
        return -1;
    }
}

示例:

输入：
7
7 6 9 5 10 8 4
输出：[4, 5, 8, 10]

解法粗陋，如有改进意见，欢迎评价。