my O(k) java solution,it is fast 1ms


  • 0
    L
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        midOrderHelper(list,root,k);
        return list.get(k-1);
    }
    
    private void midOrderHelper(List<Integer> list,TreeNode node,int k){
         if(list.size() >= k) return;
         if(node == null) return;
         if(node.left != null) midOrderHelper(list,node.left,k);
         list.add(node.val);
         if(node.right != null)  midOrderHelper(list,node.right,k);
    }

  • 0
    I

    It's not really O(k). Imagine your tree consists of only left child nodes. In that case, it would be O(N + K) ~ O(N). This is in simple order traversal. It also takes additional O(N) space, because again assuming all children are left recursion takes space for every level besides your list.

    Same thing here without list:

    public int kthSmallest(TreeNode root, int k) {
            
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode curr = root;
            
            while(k > 0) {
                if(curr == null) {
                    TreeNode top = st.pop();
                    curr = top.right;
                    k--;
                    
                    if(k == 0) {
                        curr = top;
                        break;
                    }
                } else {
                    st.push(curr);
                    curr = curr.left;
                }
            }
            
            return curr.val;
        }

Log in to reply
 

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