[数据结构与算法]二叉搜索树中第k大和第k小结点

题目

• 查找二叉搜索中第k大和第k小结点

解法

• 构建二叉树

public class BSTNode<T extends Comparable<T>> {
    T key;
    BSTNode<T> left;
    BSTNode<T> right;
    BSTNode<T> parent;

    public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

• 中序遍历

   private static void inOrder(BSTNode<Integer> tree, ArrayList<BSTNode> nodeList) {
        if (tree != null) {
            inOrder(tree.left, nodeList);
            nodeList.add(tree);
            inOrder(tree.right, nodeList);
        }

    }

• 查找第k大结点

 /**
     * 查找第k大结点
     *
     * @param tree
     * @param k    第几个
     * @return
     */
    public static BSTNode findMaxKNode(BSTNode<Integer> tree, int k) {
        if (tree == null || k < 1) return null;
        // 中序遍历tree
        ArrayList<BSTNode> nodeList = new ArrayList();
        inOrder(tree, nodeList);
        if (nodeList.size() < k) return null;
        return nodeList.get(k-1);
    }

• 查找第k小结点

 /**
     * 查找第k小结点
     *
     * @param tree
     * @param k    第几个
     * @return
     */
    public static BSTNode findMinKNode(BSTNode<Integer> tree, int k) {
        if (tree == null || k < 1) return null;
        // 中序遍历tree
        ArrayList<BSTNode> nodeList = new ArrayList();
        inOrder(tree, nodeList);
        if (nodeList.size() < k) return null;
        return nodeList.get((nodeList.size()-k));
    }