My recursive and iterative solutions in C++


  • 1
    D

    Iteration:

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

    Recursion:

    class Solution {
    int count = 0;
    public:
    int kthSmallest(TreeNode* root, int k) {
        int l = 0, r = 0;
        if (root->left != NULL) l = kthSmallest(root->left, k);
        count++;
        if (count == k) return root->val;
        if (root->right != NULL) r = kthSmallest(root->right, k);
        return l +r;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.