Kth Smallest Element In Array

https://leetcode.com/problems/kth-smallest-element-in-a-bst

평가

결과 : 성공
풀이시간 : 20분

푸는 건 금방 풀었는데, 아이디어가 굉장히 장황하네요.
이 글은 추후에 삭제할 생각입니다. 제 글을 보면 오히려 헷갈릴 거 같아요.
더 단순하게 생각하는 연습이 필요할 것 같습니다.
문제를 풀기는 풀었지만 난이도가 어려워지면 풀지 못할 것 같습니다.

아이디어

중위순회를 통해 문제를 풀 수 있습니다.
현재 노드 N의 순서를 알기 위해서는 왼쪽 SubTree의 크기를 구합니다.

1. 왼쪽 자식에 들러서 왼쪽 SubTree에 몇 개의 원소가 있는지 확인합니다.
2. 오른쪽 Sub Tree에 몇 개의 원소가 있는지 확인합니다.
3. 왼쪽 SubTree 원소 개수 + 1 + 오른쪽 SubTree 를 부모에게 전달합니다.
4. 부모노드에서 1-3을 반복합니다.

정답코드

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    static int answer = -1;
    public int kthSmallest(TreeNode root, int k) {
        findValue(root, k, 0, 0);

        return answer;
    }

    public int findValue(TreeNode root, int k, Integer now, Integer count) {
        if (root == null) {
            return 0;
        }
        // System.out.println(root.val + "에서 현재 인덱스 " + now);

        int leftCount = findValue(root.left, k, now, count);
        count = leftCount + 1;
        now += count; // 인덱스 번호

        if (now == k) {
            answer = root.val;
        }

        // n+1 < k면 더 볼필요 없음
        int rightCnt = findValue(root.right, k, now, count);
        return count + rightCnt;

        
    }
}