Java题解 | #第k轻的牛牛#
第k轻的牛牛
https://www.nowcoder.com/practice/d3b31f055b1640d9b10de0a6f2b8e6f3
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
// 创建存储节点值的列表
ArrayList<Integer> list = new ArrayList<>();
// 中序遍历二叉树并将节点值存储在列表中
inorderTraversal(root, list);
// 返回第 k 小的数
return list.get(k - 1);
}
private void inorderTraversal(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}
// 中序遍历左子树
inorderTraversal(node.left, list);
// 将当前节点值添加到列表中
list.add(node.val);
// 中序遍历右子树
inorderTraversal(node.right, list);
}
}
这道题主要考察二叉树的中序遍历和数组操作。
解题思路大纲如下：
- 创建一个存储节点值的列表。
- 使用中序遍历的方法遍历二叉树，并将节点值依次添加到列表中。
- 返回列表中第 k 个位置的值作为结果。
具体实现时，可以按照以下步骤进行：
- 创建一个
ArrayList类型的列表用于存储节点值。 - 定义一个内部方法
inorderTraversal，接收当前节点node和存储节点值的列表list作为参数。 - 在
inorderTraversal方法中，递归地进行中序遍历：若当前节点为空，则直接返回。先中序遍历左子树，调用 inorderTraversal(node.left, list)。将当前节点的值添加到列表中，即 list.add(node.val)。最后中序遍历右子树，调用 inorderTraversal(node.right, list)。 - 调用
inorderTraversal方法，传入根节点和列表对象，进行中序遍历。 - 返回列表中第 k 个位置的值，即
return list.get(k - 1)。