My C++ solution, 20ms, recursive algorithm, use preorder traverse


  • 0
    B
    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            int res;
            tree_nodes(root, k, res);
            return res;
        }
    private:
        void tree_nodes(TreeNode* root, int &k, int &res){
            if(!root || k <= 0)
                return;
            // check left children
            tree_nodes(root->left, k, res);
            if(k <= 0)
                return;
            else if(k == 1){
                res = root->val;
                --k;
                return;
            }else{
                --k;
                tree_nodes(root->right, k, res);
            }
        }
    };

  • 0
    M

    It's inorder traversal: you check left chindren, then root itself, then right children.


Log in to reply
 

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