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

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

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

思路分析

中序遍历

参考代码

func kthSmallest(root *TreeNode, k int) int {
	var stack []*TreeNode
	cur := root
	count := 0

	for cur != nil || len(stack) > 0 {
		// 将左子树的节点依次压入栈中
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}

		// 弹出栈顶节点
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		// 计数
		count++
		if count == k {
			return cur.Val
		}

		// 遍历右子树
		cur = cur.Right
	}

	// 如果 k 超出范围，返回 -1
	return -1
}

func kthSmallest(root *TreeNode, k int) int {
	count := 0
	var res int

	// 中序遍历函数
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		// 先遍历左子树
		inorder(node.Left)
		// 访问当前节点
		count++
		// 如果当前节点是第 k 个元素，则记录结果
		if count == k {
			res = node.Val
			return
		}
		// 遍历右子树
		inorder(node.Right)
	}

	inorder(root)
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/50140221