Java题解 | #第k轻的牛牛#

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

这道题主要考察二叉树的中序遍历和数组操作。

解题思路大纲如下：

1. 创建一个存储节点值的列表。
2. 使用中序遍历的方法遍历二叉树，并将节点值依次添加到列表中。
3. 返回列表中第 k 个位置的值作为结果。

具体实现时，可以按照以下步骤进行：

1. 创建一个 ArrayList 类型的列表用于存储节点值。
2. 定义一个内部方法 inorderTraversal，接收当前节点 node 和存储节点值的列表 list 作为参数。
3. 在 inorderTraversal 方法中，递归地进行中序遍历：若当前节点为空，则直接返回。先中序遍历左子树，调用 inorderTraversal(node.left, list)。将当前节点的值添加到列表中，即 list.add(node.val)。最后中序遍历右子树，调用 inorderTraversal(node.right, list)。
4. 调用 inorderTraversal 方法，传入根节点和列表对象，进行中序遍历。
5. 返回列表中第 k 个位置的值，即 return list.get(k - 1)。