Share my 2ms java solution with dynamic programming and in-order traversal


  • 0
    Z

    import java.util.ArrayList;

    public class Solution {

    class Boolean{
        
        public boolean bool;
        
        public Boolean(boolean bool){
            this.bool = bool;
        }
    }
    
    
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Boolean finished = new Boolean(false);
        kthSmallestHelper(root,k,arr,finished);
        return arr.get(k-1);
    }
    
    private void kthSmallestHelper(TreeNode root, int k, ArrayList<Integer> arr, Boolean finished){
        if(finished.bool || root==null){
            return;
        }
        kthSmallestHelper(root.left,k,arr,finished);
        arr.add(root.val);
        if(arr.size()==k){
            finished.bool = true;
            return;
        }
        kthSmallestHelper(root.right,k,arr,finished);
    }
    

    }


  • 0
    T

    You don't need the list of k-1 elements to determine the kth one. This solution uses O(k) space, while O(1) would be enough.


Log in to reply
 

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