【Leetcode每日一题】 递归 - 二叉搜索树中第K小的元素（难度⭐⭐）（56）

1. 题目解析

题目链接：230. 二叉搜索树中第K小的元素

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

中序遍历是二叉树遍历中的一种重要方式，它按照左子树、根节点、右子树的顺序访问每个节点。这种方式特别常用于二叉搜索树的验证和相关题目中。

• 二叉搜索树有一个特殊的性质：其中序遍历的结果一定是一个严格递增的序列。

算法流程如下：

1. 初始化全局计数器：在主函数中，我们定义一个全局变量count，并将其初始化为k的值。这个计数器将用于跟踪已经遍历的节点数，以便在找到目标节点时及时停止遍历。

2. 设计递归函数：我们定义一个递归函数dfs(TreeNode* root)，该函数负责在树中进行中序遍历，并返回第k个节点。

3. 递归函数的具体流程：

   • 处理空节点：如果当前节点为空（即已经遍历到叶子节点的下一层），则返回-1，表示未找到目标节点。
   • 递归左子树：首先，我们递归调用dfs函数在左子树中查找目标节点，并将结果保存在变量retleft中。
     • 剪枝操作：如果retleft不等于-1，说明在左子树中已经找到了目标节点，此时我们可以直接返回retleft，无需继续执行后续代码。
   • 处理当前节点：如果左子树中没有找到目标节点，我们检查当前节点是否符合条件（即是否为第k个节点）。
     • 返回结果：如果当前节点符合条件，我们直接返回当前节点。
   • 递归右子树：如果当前节点不符合条件，我们继续在右子树中查找目标节点。

3.代码编写

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
    int ret, count;
public:
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if(root == nullptr || count == 0) return;
        dfs(root->left);
        count--;
        if(count == 0)
        {
            ret = root->val;
            return;
        } 
        dfs(root->right);
    }
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~