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

链接：230.二叉搜索树中第K小的元素
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

题解 1 - java

• 编辑时间：2020-02-24
• 执行用时：1ms
• 内存消耗：41.3MB
• 编程语言：java
• 解法介绍：中序遍历储存值后直接获取第 k 个值。

class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public int kthSmallest(TreeNode root, int k) {
    	inorder(root);
    	return list.get(k-1);
    }
	public void inorder(TreeNode node) {
		if (node.left != null)
			inorder(node.left);
		list.add(node.val);
		if (node.right != null)
			inorder(node.right);
	}
}

题解 2 - typescript

• 编辑时间：2021-10-17
• 执行用时：100ms
• 内存消耗：44.7MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function kthSmallest(root: TreeNode | null, k: number): number {
  let ans!: number;
  dfs(root);
  return ans;
  function dfs(node: TreeNode | null): void {
    if (node === null) return;
    dfs(node.left);
    if (--k === 0) {
      ans = node.val;
      return;
    }
    dfs(node.right);
  }
}