[ Top Interview 150 ] 230. Kth Smallest Element in a BST

문제

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.

• Input : Binary Search Tree의 root node

• Output : Binary Search Tree에서 k번째로 작은 값

• 주어진 코드

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
  
      TreeNode() {}
      TreeNode(int val) {this.val = val;}
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

알고리즘 전략

• 알고리즘 기본 전략

  1. 자신의 왼쪽 하위 노드가 몇개 있는지를 통해 자신이 몇번째 노드인지 확인한다.
  2. 자신이 a 번째 노드라고 하자.
     1. k < a일 때, 앞의 노드의 k번째 노드를 찾는다.
     2. k > a일 때, 뒤의 노드의 k - a번째 노드를 찾는다.
     3. k == a일 때, 해당 노드의 val 값을 반환

• 하위 노드의 개수를 세는 방법

  • 왼쪽 노드의 개수 + 오른쪽 노드의 개수 + 1 (자기 자신)
  • null일 경우에는 0을 반환
  • 재귀적으로 개수를 계산해 나간다.

문제 답안

class Solution {

    public int kthSmallest(TreeNode root, int k) {
        int order = countNodes(root.left) + 1;

        if (k < order) {
            return kthSmallest(root.left, k);
        }
        if (k > order) {
            return kthSmallest(root.right, k - order);
        }
        return root.val;
    }

    private int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int count = 1;
        count += countNodes(root.left);
        count += countNodes(root.right);
        return count;
    }
}