230.M 二叉搜索树中第 K 小的元素

Problem: 230. 二叉搜索树中第 K 小的元素

思路

利用二叉树中序遍历是递增的特征，取出第k个被遍历的数

Code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
	var stack []*TreeNode
	i := 0
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		root = stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]

		i++
		if i == k {
			return root.Val
		}

		root = root.Right
	}

	return -1
}