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

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
示例1
输入：{5,3,7,2,4,6,8},3
返回值：4
说明：按结点数值大小顺序第三小结点的值为4

题目分析

想要获得第k小的结点，可以对二叉搜索树进行中序遍历（左-根-右），使用count计算从最左边（最小结点）开始，每经过一个结点，count加1，直到count == k，当前结点即为目标结点。

解题思路

方法1：递归法
中序遍历树，可以直接使用递归方法，同时使用一个全局TreeNode来记录结果结点，以及count来统计已经访问的结点个数。

方法2：非递归
中序遍历树，可以通过stack进行非递归遍历，同理使用count来统计访问的结点个数，当count==k时，当前结点即为目标结点。

代码实现

方法1：递归法

    TreeNode res = null;
    int count = 0;
    TreeNode KthNode(TreeNode pRoot, int k) {
        if(pRoot == null || count > k) return null;
        KthNode(pRoot.left, k);
        // 中序遍历，从最左结点开始计算个数
        count++;
        if(count == k){
            // 当已经遍历到了第k个结点，直接返回
            res = pRoot;
            return res;
        }
        // 左边结点数小于k,继续遍历右边的
        KthNode(pRoot.right, k);
        return res;
    }

时间复杂度：O(n)，在递归过程中，至少需要遍历树中的k个结点，最差情况是遍历全部的结点；
空间复杂度：O(n)，栈的递归深度与遍历的结点数相同，最差是整个树的结点数量n；

方法2：非递归

    TreeNode KthNode(TreeNode pRoot, int k) {
        if(k<=0) return null;
        TreeNode res = null;
        // 使用栈来循环遍历树
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int count = 0;
        // 循环中序遍历二叉树
        while(pRoot!=null || !stack.isEmpty()){
            while(pRoot != null){
                // 中序遍历，将根节点先放入栈中，直到最左结点
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            if(!stack.isEmpty()){
                // 从最左节点开始计数
                TreeNode tem = stack.pop();
                count++;
                if(count == k){
                    res = tem;
                    break;
                }
                pRoot = tem.right;
            }
        }
       return res;
    }

时间复杂度：O(n)，在循环过程中，至少需要遍历树中的k个结点，最差情况是遍历全部的结点；
空间复杂度：O(n)，栈中最多存储整个树的结点数量n。