一、知识点:
中序遍历、递归、二叉树
二、文字分析:
反向中序遍历的递归实现:我们首先定义了两个全局变量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); } }