题解 | #二叉树之寻找第k大#
二叉树之寻找第k大
https://www.nowcoder.com/practice/8e5f73fa3f1a407eb7d0b0d7a105805e
知识点:
中序遍历
解题思路:
二次搜索树的中序遍历(左-中-右)是一个递增序列,那么我们反过来遍历(右-中-左)就是递减序列,我们只需要在中序位置判断当前节点是否是第k个即可。
语言:
Golang
package main import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param k int整型 * @return int整型 */ func kthLargest( root *TreeNode , k int ) int { // write code here ans:=0 count:=0 var dfs func(root *TreeNode,k int) dfs=func(root *TreeNode,k int){ if root == nil{ return } dfs(root.Right,k) count++ if count == k{ ans = root.Val return } dfs(root.Left,k) } dfs(root,k) return ans }