题解 | #二叉搜索树的第k个结点#

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

方法一：递归法求解

求解思路
我们采用递归的方式，不断递归深入根节点的左孩子，直到碰到空节点为止，然后回溯输出当前节点。再以同样的方式递归遍历其右孩子。在此期间，每访问一个节点，我们都对k进行减一操作，直到k为0，说明该节点即为第k个节点，即找到题目所要的第k个结点

图片说明

解题代码

class Solution {
public:
    int m;
    TreeNode* hyans; // 存储结果
    void dfs (TreeNode* p)
    {
        if(!p || m < 1) return; // 不满足条件直接返回NULL
        dfs(p -> left); // 对左子树进行递归
        if(m == 1) hyans = p; // 最左边结点
        if(--m > 0) dfs(p -> right); // 同样对右子树进行递归
    }
    TreeNode* KthNode (TreeNode* p, unsigned int k)
    {
        hyans = NULL; // 初始化 ans=NULL 不满足条件返回NULL
        m = k;
        dfs(p); // 进行dfs
        return hyans; // 返回结果
    }
};

复杂度分析
时间复杂度：递归法，时间复杂度为 $O(N)$ ,N为二叉树的深度
空间复杂度：没有引入新的内存地址空间，空间复杂度为 $O(1)$

方法二：非递归法求解

求解思路
我们可以利用栈来模拟递归遍历，首先根入栈，然后令根节点的左孩子不断入栈直到为空，弹出栈顶，令其右孩子入栈，重复以上操作，直到遍历结束或者访问第k个节点为止，这样即采用了非递归的方法求出本题所要求的第k个结点。

图片说明

解题代码

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot,unsigned int k)
    {
        if(!pRoot) return nullptr; // 直接返回空
        stack<TreeNode *> hyres; // 声明栈
        TreeNode* p = pRoot;
        while(!hyres.empty() || p )
        {   //res是空 or 遍历到空节点
            while(p) // 对左子树入栈
            {
                hyres.push(p);
                p = p->left;
            }
            TreeNode* node = hyres.top();
            hyres.pop();
            if((--k)==0) return node; // 返回第k个结点
            p = node->right;
        }
        return nullptr;
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O( )$
空间复杂度：声明栈，引入新的内存地址空间，因此空间复杂度为 $O(K)$ ,K为题目所要求的第K个结点。