题解 | #第k轻的牛牛#

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 *
 * @param root TreeNode类
 * @param k int整型
 * @return int整型
 */
func kthLighest(root *TreeNode, k int) int {
	// write code here
	v := 0
	dfs(root, &k, &v)
	return v
}

func dfs(root *TreeNode, k *int, v *int) {

    if *k == -1 {
        return
    }

	if root.Left != nil {
		dfs(root.Left, k, v)
	}

    *k--
	if *k == 0 {
		*v = root.Val
		return
	}

	if root.Right != nil {
		dfs(root.Right, k, v)
	}
}

解题思路

• 二叉树搜索树的特点是，每个根节点，左节点值小于根节点的值，右节点大于跟节点的值。由于这样的特点，如果通过中序遍历，就是从小到大的排序列表。
• 只要通过中序遍历的方式，每遍历一个元素k--，当k为0时，就找到了第k个元素。这个时候就可以递归结束了，所以k=-1时，直接返回。
• 注意：k和v在递归函数里，用的是地址类型。