前言：參加公司技術(shù)考試缤骨，時(shí)間90分鐘，包括20多道邏輯推理題和20多道計(jì)算機(jī)考研四門(mén)課的題后，還有最后一道編程題：輸入節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)各個(gè)值妓羊，輸出根據(jù)各節(jié)點(diǎn)值形成的二叉搜索樹(shù)的最后兩層的節(jié)點(diǎn)序列。當(dāng)時(shí)時(shí)間不夠沒(méi)做出來(lái)稍计，中午抽空做了下躁绸。
解題思路：首先是建樹(shù)，我的辦法是在搜索時(shí)把各個(gè)值插入到相應(yīng)位置臣嚣，并記錄各個(gè)節(jié)點(diǎn)所在的層數(shù)净刮，建好后根據(jù)層數(shù)比較輸出序列。
代碼如下：

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);
    }

    /**
     * 二叉搜索樹(shù)算法調(diào)用
     * @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);//獲取二叉樹(shù)最大層數(shù)
            maxLayer = maxLayer<currentLayer?currentLayer:maxLayer;
        }
        preOrder(root,maxLayer);
        System.out.println(list);
    }

    /**
     * 先序遍歷硅则，輸出為有序數(shù)列
     * @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 根節(jié)點(diǎn)
     * @param node 待插入節(jié)點(diǎn)淹父，存在則不插入
     * @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]

解法粗陋，如有改進(jìn)意見(jiàn)怎虫，歡迎評(píng)價(jià)暑认。