JAVA recursive 0ms and iterative 3ms solutions


  • 0
    P

    recursive solution

    public class Solution {
    int ans = 0;
    public int kthSmallest(TreeNode root, int k) {
        TreeNode x = new TreeNode(k);
        helper(root, x);
        return ans;
    }
    
    public void helper(TreeNode root , TreeNode x){
        if(root == null || x.val<0) return;
        
        helper(root.left , x);
        x.val--;
        if(x.val==0){
            ans = root.val;
            return;
        }
        helper(root.right , x);
    }
    

    iterative solution

    public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        root = root.left;
        while(root!=null || !stack.empty()){
            if(root!=null){
                stack.push(root);
                root = root.left;
            }
            else{
                TreeNode temp = stack.pop();
                if(k==1) return temp.val;
                else k--;
                root = temp.right;
            }
        }
        return 1;   
    }

Log in to reply
 

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