一、题目描述

JZ62 二叉搜索树的第k个结点
题目大意：给定一颗二叉搜索树，请找出其中第k小的TreeNode节点
注意审题：二叉搜索树，第k小

二、算法1 （中序遍历（递归））

解题思路

1. 二叉搜索树的一个性质就是它的中序遍历顺序得到的序列是有序的
2. 根据这个性质我们可以想到一个办法就是先将中序遍历序列存下来，最后返回第k的数即可，但是会用到额外的空间，我们可以用一个全局变量记录当前节点是第第几个，在中序遍历的过程中更新即可，当遍历到第k个节点时记录一下结点指针即可

代码实现 （C++11）

class Solution {
public:
    TreeNode* ans = nullptr;
    int m = 0;
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        dfs(pRoot, k);
        return ans;
    }

    void dfs(TreeNode* root, int k){
        if(!root) return;
        dfs(root->left, k);         // 向左递归
        ++m;    // 计数器加1
        if(m == k) ans = root;      // 当找到第k个节点，记录到答案中
        dfs(root->right, k);        // 向右递归
    }
};

小小优化

为了稍微再优化一下时间，我们希望在找到第k个元素后就直接返回，而不是继续遍历剩下的结点，因此我们可以为递归函数设置一个布尔返回值，当找到元素时直接返回true

bool dfs(TreeNode* root, int k){
        if(!root) return false;
        if(dfs(root->left, k)) return true;    // 若找到了节点，直接中断并向上返回
        ++m;
        if(m == k){
            ans = root;
            return true;
            }
        if(dfs(root->right, k)) return true;
        return false;
    }

时间复杂度：O(n), n为二叉树节点的个数
空间复杂度：O(n), 递归使用的栈空间

三、算法2（中序遍历（栈））

解题思路

1. 递归的中序遍历十分容易理解也很好实现，但是非递归的中序遍历方法我们也应该掌握，需要使用栈来模拟递归的过程
2. 由于中序遍历的顺序是 左儿子 -> 根 -> 右儿子，因此我们先从根节点开始不断往左走，并将路上的节点依次入栈，走到底后开始出栈，然后将出栈节点的右儿子作为新的虚拟根节点尝试向左走重复上诉步骤，直到遍历完所有结点结束

代码实现（C++11）

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        stack<TreeNode*> stk;    // 栈
        TreeNode* cur = pRoot;    // 先指向根节点
        while(!stk.empty() || cur != nullptr){    // 迭代条件
            if(cur != nullptr){    // 只要当前节点不为空，入栈并继续向左
                stk.push(cur);
                cur = cur->left;
            }
            else{    // 当前节点为空，出栈并计数若k为0则直接返回，否则尝试向右走
                cur = stk.top();
                stk.pop();
                if(--k == 0) return cur;    // 找到节点返回即可
                cur = cur->right;    // 尝试向右走
            }
        }
        return nullptr;    // 注意k可能为0或大于二叉树的结点数量，此时返回null
    }
};

时间复杂度：O(n)，n为二叉树节点的数量
空间复杂度：O(n)，辅助栈使用的空间