剑指offer（62）：二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

思路：中序遍历的第k个结点即为所求

C++f非递归实现 ：

class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(!pRoot) return NULL;
        stack<TreeNode*> sTree;
        TreeNode* p = pRoot;//临时结点
        int count = 0;//计数
        
        while(!sTree.empty()||p){
            if(p){
                sTree.push(p);
                p = p->left;
            }else{
                p = sTree.top();
                sTree.pop();
                count++;
                if(count==k)
                    return p;
                p = p->right;
            }
        }//while
        return NULL;
    }

    
};

C++递归实现：

这里需要注意的是，递归的返回，刚开始只写了当count==k的时候才进行返回，导致程序出错，在count！=k的时候也应该有结点的返回。

class Solution {
    
public:
    int count = 0;
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot){
            TreeNode* node = KthNode(pRoot->left, k);
            if(node) return node;
            count++;
            if(count == k)
                return pRoot;
            node = KthNode(pRoot->right, k);
            if(node) return node;
        }
        else return NULL;
        
    }
};

java实现：

import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null) return null;
        int count = 0;
        Stack<TreeNode> sTree = new Stack<>();
        TreeNode p = pRoot;//临时结点
        while(!sTree.isEmpty()||p!=null){
            while(p!=null){
                sTree.add(p);
                p = p.left;
            }
            p = sTree.pop();
            count++;
            if(count == k) return p;
            p = p.right;
        }
        return null;
    }
}