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

思路：中序遍历。在二叉搜索树中，中序遍历的遍历顺序就是在从小到大遍历节点值，所以遍历到的第k个节点值就是答案。每次递归完左子树，在根节点的操作中，把k减少1，表示按照中序遍历的顺序访问到了一个节点。当k变为0时，就说明找到了要找的节点的值，用一个外部变量ans记录。

1.确定递归函数的参数和返回值类型：

（1）参数：二叉树的根节点和整数k。

（2）返回值类型：返回int整数结果ans。

（3）全局变量：k表示需要搜索第k小的节点值，ans表示对应的整数结果。

private int ans; private int k; public int kthSmallest(TreeNode root, int k)

2.确定终止条件：如果节点为空或k为0，子函数dfs直接return；

if(node == null || k == 0){ return; }

3.确定单层递归的逻辑：中序遍历，根值判断k是否减为0，如果减为0则用ans记录此时的节点值。

dfs(node.left); //左 if(--k == 0){ ans = node.val; //根 } dfs(node.right); //右

4.复杂度分析：

（1）时间复杂度：O(n)，其中n是二叉树的大小（节点个数）。

（2）空间复杂度：O(h)，其中h是树高，递归需要O(h)的栈空间。最坏情况下树是一条链，h = n，空间复杂度退化为O(n)。

附代码：

class Solution { private int ans; private int k; public int kthSmallest(TreeNode root, int k) { this.k = k; dfs(root); return ans; } private void dfs(TreeNode node){ if(node == null || k == 0){ return; } dfs(node.left); //左 if(--k == 0){ ans = node.val; //根 } dfs(node.right); //右 } }