题解 | #二叉搜索树的第k个节点#
二叉搜索树的第k个节点
https://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff
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)
}
