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

题目描述

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

考查知识点

• 二叉搜索树(bst)
• 树的遍历
• 二叉搜索树中序遍历的特殊性质

分析

1.首先我们给出二叉搜索数的定义:
如果一颗二叉树，满足如下条件

• 若其结点的左子树不空，且左子树上所有结点的值均不大于它的根结点的值。
• 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
  则我们称这样的二叉数为二叉搜索树
  如下图即为一颗二叉搜索树(以下统称为bst), 对于任意节点，其左子树的所有节点一定不大于该节点，其右子树的节点一定不小于该节点
  
  2.树的遍历: 关于树的四种遍历方式我在JZ61这道题中已经介绍，这里不做赘述，这里给需要的读者附上那题的链接:
  https://blog.nowcoder.net/n/50edaca0531e4693a2db6e0575143d72
  3.二叉搜索树中序遍历的特殊性质
  关于这个性质当结论背过即可，该性质为:bst中序遍历得到的序列即为将bst上所有节点按从小到大排序的序列，可以举个例子说明其正确性:
  

解法一:使用递归实现中序遍历，因为bst的中序遍历结果即为节点的值从小到大排序的结果，所以通过一个全局变量记录当前遍历至第k个即可

• 优点:代码简洁，实现简单
• 缺点:递归所耗费的时间和空间比迭代实现大得多，若是多二者要求比较苛刻时要慎重考虑
  正确代码及注释如下

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    int index = 0;
    TreeNode* ans = nullptr;
    TreeNode* KthNode(TreeNode* pRoot, int k) {
        if(!pRoot) return nullptr;    //边界处理
        KthNode(pRoot->left, k);      //处理左子树
        index ++ ;
        if(index == k) ans = pRoot;   //处理当前节点
        KthNode(pRoot->right, k);     //处理右子树
        return ans;                   //返回结果
    }
};

时间复杂度:空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。时间复杂度应该为O(n)，根据公式T(n)=2T(n/2)+1=2(2T(n/4)+1)+1=2^logn+2^(logn-1)+...+2+1 ~= n，所以时间复杂度为O(n)。

方法二:通过迭代的方式实现中序遍历，依旧是使用一个变量记录遍历至第k个

• 优点:占用时间，空间少，速度较递归实现快
• 缺点:代码复杂，实现难度比递归写法大

正确代码及注释如下

/*
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) {
        if(!pRoot || k == 0) return nullptr;   //空树与边界处理
        int idx = 0;
        stack<TreeNode*> stk;          //用栈模拟中序遍历的递归与回溯过程
        while (pRoot || stk.size()) {
            while (pRoot) {        //先遍历左子树
                stk.push(pRoot);
                pRoot = pRoot->left;  
            }
            pRoot = stk.top();
            stk.pop();                        //模拟回溯
            idx ++;
            if(idx == k) return pRoot;        //再遍历当前节点
            pRoot = pRoot->right; //最后遍历右子树
        }
        return nullptr;
    }


};

时间复杂度分析:由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利用一个辅助栈来进行每个节点的存储打印，所以每个节点都要进栈和出栈，不过是根据那种遍历方式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数。