题解 | #二叉搜索树的第k个节点#

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)
    }
}