50题 第42天 二叉搜索树中第K小的元素

• 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
• 说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
• 链接: 力扣.
• 我的代码如下：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {List<Integer> list = new ArrayList();public void dfs(TreeNode root){if(root == null)return ;dfs(root.left);list.add(root.val);dfs(root.right);}public int kthSmallest(TreeNode root, int k) {if(root == null) return -1;dfs(root);return list.get(k-1);}
}

运行结果

• 写着道题的时候比较谨慎，特地去查了一下二叉搜索树和二叉树有没有什么不同，然后发现二叉搜索树是有明确定义的（二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。来源：百度百科），这样一来，如果按照中序遍历的方法，按“左根右”的顺把二叉树变成list，得到的就是顺序排列的。这样我们就不难得到第k小的数了。注意，空树也是二叉搜索树，在这道题里要单独分类。