package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
func KthNode( proot *TreeNode , k int ) int {
// write code here
lenTree := 0
getSize(proot, &lenTree)
if proot == nil || k > lenTree || k <= 0{
return -1
}
res := 0
inOrder(proot, &k, &res)
return res
}
func inOrder(proot *TreeNode, k *int, res *int) { // 分析知本题应使用中序遍历解题
if proot == nil { // 1.如果当前节点为空，则直接返回
return
}
if proot.Left != nil { // 2.否则，若当前节点的左节点存在，中序遍历左节点（即一直遍历到整棵树的最左边）
inOrder(proot.Left, k, res)
}
(*k)-- // 3.到此对k减1，表明访问到了第一小的元素
if *k == 0 { // 4.判断k是否为0，若是，说明当前节点即为第k小的元素，将值赋给res，并直接返回
*res = proot.Val
return
}
if proot.Right != nil { // 5.若k不为0，说明当前节点不是第k小的元素，中序遍历右节点
inOrder(proot.Right, k, res)
}
}
func getSize(proot *TreeNode, lenTree *int) { // 遍历所有元素来统计该树的节点个数，用于与k比较
if proot != nil {
*lenTree++
getSize(proot.Left, lenTree)
getSize(proot.Right, lenTree)
}
}
