算法记录

LeetCode 题目：

 &emsp;&emsp;给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。 <hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

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

二、分析

给出的结构是一个二叉搜索树，那么我们只需要遍历一般当前的二叉树拿到升序数组返回对应位置上的数即可，但是这样每次都需要将整个二叉树都遍历一遍，我们能不能只遍历到当前位数据就可以了呢。

按照上面的想法，我们来分析，中序遍历每访问一次根节点也就意味着我们拿到了一个较小的数据（相对于剩下的二叉树节点数据），也就是离我们需要寻找的位数就更近一步。

那我们就可以遍历根节点的时候就将 k 减一，如果减到 0 也就意味着当前访问的节点就是遍历完之后的第 k 小的数据，也就可以直接返回。

这里需要注意的 k 值的携带，不能直接用参数去携带，因为 java 只有值传递，需要将其设置为全局变量。

class Solution {    private Integer number;    public int kthSmallest(TreeNode root, int k) {        number = k;        return dfs(root);    }    private int dfs(TreeNode root) {        if(root == null) return -1;        int left = dfs(root.left);        if(left != -1) return left;        number--;        if(number == 0) return root.val;        return dfs(root.right);    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

二插搜索树的性质应用。

原文：https://juejin.cn/post/7100924106828169230