题目:
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
思路:
题目中二叉树为二叉搜索树,很容易想到将数中序遍历,得到的顺序即为排序顺序,从而很容易就得到第k小的元素。而实现中序遍历
有递归和循环两种写法。
代码:
1.递归:
1 | private int count = 0; |
2.排序:
1 | public int kthSmallest1(TreeNode root, int k) { |
复杂度分析及总结:
1.递归:
时间复杂度:
O(n)。
空间复杂度:
O(n)。
2.循环:
时间复杂度:
O(n)。
空间复杂度:
O(n)。
总结:
注意递归写法中需要利用全局变量记录第k小的值。