题目描述

给定一棵二叉搜索树，请找出其中的第 k 小的结点。

你可以假设树和 k 都存在，并且 1≤k≤ 树的总结点数。

样例

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

    2
   / \
  1   3

输出：3

算法

(二叉搜索树) $O(n)$

因为二叉搜索树的中序遍历是有序的，根据这个特点，可以在中序遍历的过程中传入 $k$，每次遍历一个节点 k -- ，当 k = 0 时当前节点就是二叉树的第 $k$ 小的节点

剪枝优化：只有当 k > 0 时才继续进行中序遍历寻找答案，时间复杂度可以优化为 $O(k)$

时间复杂度

中序遍历的过程需要遍历整棵树，时间复杂度为 $O(n)$，优化后的时间复杂度可以降到 $O(k)$

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* ans;

    TreeNode* kthNode(TreeNode* root, int k) {
        dfs(root, k);
        return ans;
    }

    void dfs(TreeNode* root, int &k)
    {
        if (!root) return ;

        if (k > 0) dfs(root->left, k);

        k -- ;
        if (!k) ans = root;

        if (k > 0) dfs(root->right, k);
    }
};