一、知识点:
中序遍历、递归、二叉树
二、文字分析:
反向中序遍历的递归实现:我们首先定义了两个全局变量count和result,分别用于记录当前遍历的节点是第几个节点和第k大的牛的编号。通过递归方式获取二叉搜索树的节点总数,并根据节点总数计算目标节点的计数器值。然后,通过递归方式进行反向中序遍历,首先递归遍历右子树,然后将计数器加1,并判断计数器的值是否等于目标值。如果是,则更新result为当前节点的值,并立即返回。如果不是,则继续递归遍历左子树。
时间复杂度为O(N),空间复杂度为O(N)。
三、编程语言:
java
四、正确代码:
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 {
private int count = 0; // 计数器,记录当前节点是第几个节点
private int result = 0; // 记录第k大的牛的编号
public int kthLargest(TreeNode root, int k) {
reverseInorderTraversal(root, k); // 反向中序遍历
return result;
}
private void reverseInorderTraversal(TreeNode node, int k) {
if (node == null) {
return;
}
reverseInorderTraversal(node.right, k);
count++;
if (count == k) {
result = node.val;
return;
}
reverseInorderTraversal(node.left, k);
}
}

京公网安备 11010502036488号