Java Iterative and Recoursive solution. up to 0ms


  • 0
    S

    Iterative
    This version does 2 ms. to have 0ms replace stack with TreeNode[] and add index counter.

    public int kthSmallest(TreeNode root, int k) {
    	int n = 0;
    	TreeNode current = root;
    	Stack<TreeNode> lefts = new Stack<>();
    	while(current != null || !lefts.isEmpty()){
    		if(current != null){
    			if(current.left != null){
    				lefts.add(current);
    				current = current.left;
    			}
    			else {
    				n++;
    				if(n == k){
    					return current.val;
    				}
    				current = current.right;
    			}
    		} 
    		else {
    			current = lefts.pop();
    			n++;
    			if(n == k){
    				return current.val;
    			}
    			current = current.right;
    		}
    	}
    	return -1;
    }
    

    Recoursive
    Does 1 ms

    public class Solution {
    	private int cnt = 0;
        public int kthSmallest(TreeNode root, int k) {
            int result = 0;
            if(root != null){
        		result = kthSmallest(root.left,k);
        		cnt++;
        		if(cnt == k){
        			return root.val;
        		}
        		result += kthSmallest(root.right,k);
            }
    		return result;
        }
    }

Log in to reply
 

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