C++ simple solution with inorder traversal


  • 0
    Y
    int kthSmallest(TreeNode* root, int k) {
            if(!root || k<=0) return INT_MIN;
            stack<TreeNode*> my_stack;
            while(root || !my_stack.empty()){
                if(root){
                    my_stack.push(root);
                    root = root->left;
                } else {
                    root = my_stack.top();
                    -- k;
                    if(k==0) return root->val;
                    my_stack.pop();
                    root = root->right;
                }
            }
            return INT_MIN;
        }
    

  • 0
    V

    What is the --k doing? and why is it placed at that line?


  • 0
    Y

    @ved1995 .
    This solution uses stack to do inorder traversal.
    Any tree traversal could be divided into two parts: traverse down and traverse up.

    Here, for any node, we push it to stack, and go to its left child. This is traverse down.
    When the node is null, we begin to traverse up by getting the top node from the root.

    The ELSE clause here means we are traversing up from leaf node now. And it is time to count the number.
    When k==0, then it means that current node is the kth node in this tree.


Log in to reply
 

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