每日一题(day1)

题目链接

方法一：使用栈进行中序遍历

class Solution {
public:
    int kthSmallest(TreeNode *root, int k) {
        stack<TreeNode *> ST;
        while (root != NULL || ST.size() > 0) 
        {
            while (root != NULL) 
            {
                ST.push(root);
                root = root->left;
            }
            root = ST.top();
            ST.pop();
            --k;
            if (k == 0) 
            {
                break;
            }
            root = root->right;
        }
        return root->val;
    }
};

方法二：分治
对于当前结点：如果其left的结点总数小于k-1。那么第k小的数一定在右子树，令node为右子结点，K为k-left-1;
对于当前节点：如果其left节点总数大于k-1。那么第K小的数一定在左子树，令node为其左子树
对于当前节点：如果其left节点总数等于k-1。那么第k小的数一定是当前节点

class Solution {
public:
    int kthSmallest(TreeNode *root, int k) 
    {
        TreeNode* node=root;
        while(node!=NULL)
        {
            int num=getnum(node->left);
            if(num==k-1)
            {
                break;
            }
            else if(num<k-1)
            {
                k-=num+1;
                node=node->right;
            }
            else
            {
                node=node->left;
            }
        }
        return node->val;
    }
    int getnum(TreeNode* root)
    {
        if(root==NULL)
            return 0;
        return 1+getnum(root->left)+getnum(root->right);
    }
};