Portfolio

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:


Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:


Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

The number of nodes in the tree is n.

1 <= k <= n <= 104

0 <= Node.val <= 104

풀이

은찬


var kthSmallest = function(root, k) {
    const arr = [];
    
    const dfs = (node) => {
        arr.push(node.val);
        
        if(node.left){
            dfs(node.left);
        }
        
        if(node.right){
            dfs(node.right);
        }
    }
    
    if(!root){
        return;
    }
    
    dfs(root);
    
    arr.sort((a, b) => a - b);
    
    return arr[k - 1];
};

재영


const check = (result, k) => {
  return result.length === k;
};

const treverseByInOrderUntilK = (node, k, result = []) => {
  if (check(result, k)) {
    return result;
  }

  if (!node.left && !node.right) {
    result.push(node.val);
    return result;
  }

  if (node.left) {
    result = treverseByInOrderUntilK(node.left, k, result);
  }

  if (!check(result, k)) {
    result.push(node.val);
  }

  if (node.right) {
    result = treverseByInOrderUntilK(node.right, k, result);
  }

  return result;
};

const kthSmallest = (root, k) => {
  return treverseByInOrderUntilK(root, k).pop();
};

효성

sort가 nlogn이라 그렇게 빠르진 않네요..!


var kthSmallest = function(root, k) {
    const arr = [];
    
    const dfs = (node) => {
        if(!node) return;
        
        arr.push(node.val);

        node.right && dfs(node.right);
        node.left && dfs(node.left);
    }
    
    dfs(root);
    arr.sort((a, b) => a - b);
    
    return arr[k -1];
};