前言
一个多月没有更新了。
正文
问题来源
本问题来自leetcode上的230题。
问题描述
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
分析：
非递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
q := root
stack := make([]*TreeNode, 0)
for q != nil || len(stack) > 0 {
for q != nil {
stack = append(stack, q)
q = q.Left
}
if len(stack) > 0 {
q = stack[len(stack)-1]
stack = stack[:len(stack)-1]
k--
if k == 0 {
return q.Val
}
q = q.Right
}
}
return 0
}
递归版本
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
node := inTrav(root, &k)
return node.Val
}
func inTrav(root *TreeNode, k *int) *TreeNode {
var node *TreeNode
if root.Left != nil {
node = inTrav(root.Left, k)
}
if node == nil {
if *k == 1 {
node = root
}
*k--
}
if node == nil && root.Right != nil {
node = inTrav(root.Right, k)
}
return node
}
总结：
勤思考。
结语
不管怎么样好好加油。
