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

二叉搜索树的第k个结点

http://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a

题目描述

给定一棵二叉搜索树，请找出其中的第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;
    }


};