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

思路

既然题中的树是二叉搜索树，所以中序遍历顺序即为从小到大的访问顺序。这一点要直接反应过来！！！
知道是中序遍历后就采用递归或非递归两种方法都可以了

方法一：递归中序遍历

递归中序的函数结构为

• 递归左子树
• 访问当前结点
• 递归右子树

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* res;                                // 采用一个全局的res指针来指向最终返回结果
    void inOrder(TreeNode*root,int &k){           // 中序遍历递归函数
        if(root==nullptr) return;                 // 遇到空指针直接返回
        inOrder(root->left,k);                    // 左子树递归
        k--;                                      // 访问结点并进行倒着计数  
        if(k==0) res=root;
        inOrder(root->right,k);                   // 右子树递归
    }
    TreeNode* KthNode(TreeNode* pRoot, int k) {    
        inOrder(pRoot, k);                        // 调用中序遍历
        return res;                               // 返回指针
    }
};

方法二：非递归中序遍历

非递归的方案需要维护一个栈，对栈的操作同样要理解成递归的方式

• 沿着左子树一直入栈到底
• 取栈顶元素访问
• 对当前栈顶元素的右子树进行同样方式的访问

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:

    TreeNode* KthNode(TreeNode* pRoot, int k) {
        TreeNode* res = NULL;
        stack<TreeNode* > s;                    // 维护一个栈
        int n = 0;                              // 初始化计数器
        TreeNode* cur = pRoot;                  // 迭代指针初始指向根节点
        while(!s.empty() || cur) {              // 判断条件：栈非空 或 cur非空
            while(cur){                         // 沿着左子树全部进栈
                s.push(cur);
                cur = cur -> left;
            }
            cur = s.top();                      // 取栈顶元素
            s.pop();
            n++;                                // 计数器+1
            if(n == k) {                        // 判断是否为第k个元素
                res = cur;
                return res;
            }
            cur = cur->right;                   // 迭代指针指向取出来的栈顶元素的右侧孩子
        }
        return res;
    }
};

两种方法的复杂度计算

• 时间复杂度：O(n)，访问每个节点
• 空间复杂度：O(n)，维护栈的空间深度