leetcode第230题（中等）

原链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/submissions/

问题描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例1

输入：root = [3,1,4,null,2], k = 1
输出：1

示例2

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

解题思路

递归中序遍历二叉搜索树，因为这种遍历方式是有序的，且顺序是从大到小。当遍历到第k个元素时返回当前节点的val值就可以了。

代码（java）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return val;
    }
    int k;
    int i=1;
    int val;
    boolean b=false;
    public void dfs(TreeNode root){
        if(b||root==null){
            return;
        }
        dfs(root.left);
        if(!b&&i==k){
            val=root.val;
            b=true;
            return;
        }
        i++;
        dfs(root.right);
    }
}

测试结果