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

package main

import "fmt"

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

var index int

func KthNode(proot *TreeNode, k int) int {
	// write code here
	res := midTravel(proot, k)
	if res == nil {
		return -1
	}
	return res.Val
}

func midTravel(node *TreeNode, targetPos int) *TreeNode {
	if node == nil {
		return nil
	}
	if res := midTravel(node.Left, targetPos); res != nil {
		return res
	}
	index += 1
	if targetPos == index {
		return node
	}
	if res := midTravel(node.Right, targetPos); res != nil {
		return res
	}
	return nil
}

func main() {
	node1 := &TreeNode{Val: 5}
	node2 := &TreeNode{Val: 3}
	node3 := &TreeNode{Val: 7}
	node4 := &TreeNode{Val: 2}
	node5 := &TreeNode{Val: 4}
	node6 := &TreeNode{Val: 6}
	node7 := &TreeNode{Val: 8}

	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Left = node6
	node3.Right = node7

	k := 3
	res := KthNode(node1, k)
	fmt.Println(res)
}