博客

知识点

1. 基础数据结构的理解和编码能力
2. 递归使用
3. 保证输入的K满足1<= K <= (节点数目)

public class 二叉搜索树的第k个节点 {

    /**
     * 索引
     */
    int index = 0;

    /**
     * 找到二叉搜索树的第k个节点
     *
     * @param root
     * @param k
     * @return
     */
    private TreeNode KthNode(TreeNode root, int k) {

        if (root != null) {

            TreeNode node = KthNode(root.left, k);

            if (node != null) {

                return node;
            }

            index++;

            if (index == k) {

                return root;
            }

            node = KthNode(root.right, k);

            if (node != null) {

                return node;
            }
        }
        return null;
    }

    /**
     * 添加节点到二叉数
     *
     * @return
     */
    private TreeNode addNode(int val, TreeNode head) {
        if (head == null) {
            head = new TreeNode(val);
            return head;
        }
        if (head.getVal() >= val) {
            head.setLeft(addNode(val, head.getLeft()));
        } else {
            head.setRight(addNode(val, head.getRight()));
        }
        return head;
    }

    /**
     * 将数组转为二叉树
     *
     * @param arr
     * @return
     */
    private TreeNode createTree(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }
        TreeNode head = new TreeNode(arr[0]);
        TreeNode point = head;
        for (int i = 1; i < arr.length; i++) {
            addNode(arr[i], point);
        }
        return head;
    }

    /**
     * 打印二叉树
     *
     * @param head
     */
    private void printTree(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.println(head.val);
        printTree(head.getLeft());
        printTree(head.getRight());
    }

    public static void main(String[] args) {

        // 生成随机数
        Random random = new Random();

        int[] arr = new int[10];

        for (int i = 1; i < 10; i++) {

            arr[i] = random.nextInt(10);
        }
        二叉搜索树的第k个节点 二叉搜索树的第k个节点 = new 二叉搜索树的第k个节点();
        TreeNode head = 二叉搜索树的第k个节点.createTree(arr);
        二叉搜索树的第k个节点.printTree(head);
        TreeNode treeNode = 二叉搜索树的第k个节点.KthNode(head, 5);
        // 当k超出不在节点范围内为空指针，自行控制
        System.out.println("二叉搜索树的第5个节点：" + treeNode.getVal());
    }


    /**
     * 节点类
     */
    @Data
    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

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

注意：本文归作者所有，未经作者允许，不得转载