首页 > 其他 > 详细

Kth Smallest Element in a BST

时间:2016-02-29 00:34:38      阅读:157      评论:0      收藏:0      [点我收藏+]

题目:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST‘s total elements.

 

cpp:

方法一:递归

class Solution {
public:
    int kthSmallest(TreeNode* root,int k){
        int result;
        inOrder(root,k,result);
        return result;
    }

    int n =0;
    void inOrder(TreeNode* root,int kth,int& kthVal){
        if(!root ) return;
        inOrder(root->left,kth,kthVal);
        n = n + 1;
        if(n == kth) {
            kthVal = root->val;
            return;
        }
        inOrder(root->right,kth,kthVal);
    }

};

方法2:栈

class Solution{
public:
    int kthSmallest(TreeNode* root,int k){
        stack<TreeNode*> stack;
        int result;
        TreeNode *cur = root;
        while(!stack.empty() || cur){
            if(cur){
                stack.push(cur);
                cur = cur->left;
            }else{
                TreeNode* temp = stack.top();
                stack.pop();
                k--;
                if(k==0) {
                    result = temp->val;
                    return result;
                }
                cur = temp->right;
            }
        }

        return result;
    }


};

 

Kth Smallest Element in a BST

原文:http://www.cnblogs.com/wxquare/p/5224995.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!