题解 | #第k轻的牛牛#

第k轻的牛牛

https://www.nowcoder.com/practice/d3b31f055b1640d9b10de0a6f2b8e6f3?tpId=354&tqId=10591747&ru=/exam/oj&qru=/ta/interview-202-top/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D354

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param k int整型
     * @return int整型
     */
    public int kthLighest (TreeNode root, int k) {
        // write code here
        List<Integer> inorderValues = new ArrayList<>();
        inorderTraversal(root, inorderValues);

        return inorderValues.get(k - 1);
    }

    private void inorderTraversal(TreeNode node, List<Integer> values) {
        if (node == null) {
            return;
        }

        inorderTraversal(node.left, values);
        values.add(node.val);
        inorderTraversal(node.right, values);

    }
}

知识点:

  1. 二叉搜索树(Binary Search Tree,BST)基本概念:了解二叉搜索树的定义和基本特点,包括左子树节点值小于根节点,右子树节点值大于根节点等。
  2. 二叉搜索树的中序遍历:了解如何通过中序遍历二叉搜索树,得到有序的节点值序列。

题目解答方法:

要解决这个问题,可以通过中序遍历二叉搜索树,得到有序的节点值序列,然后根据给定的 k,找到有序序列中第 k 个元素即可。

具体步骤如下:

  1. 创建一个数组或链表,用于存储中序遍历得到的节点值序列。
  2. 进行中序遍历二叉搜索树,将节点值按照从小到大的顺序加入数组或链表。
  3. 根据给定的 k,找到数组或链表中对应索引位置的元素,即第 k 个最小元素。
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务