[leetcode] Smallest String Starting From Leaf

문제

• 문제 링크
• 이진 트리 root가 주어진다. 각 노드는 [0, 25] 범위의 값을 가진다. 그리고 각 값은 ['a', 'z']에 대응된다. leaf 노드에서 root로 이어지는 문자열 중에, 사전적으로 가장 작은 문자열을 구해야 한다. leaf 노드는 자식 노드를 가지고 있지 않은 노드이다.
• 제약 조건
  • 트리에 있는 노드의 개수: [1, 8500]
• 예시
  

풀이

풀기 전

• 경로에 있는 문자를 모두 저장하면서 노드를 탐색해야 한다. 그리고 leaf를 만났을 때 완성된 문자열이 사전적으로 가장 작은지 확인하면 된다.
• 헷갈릴 수 있는 건 문자열을 만들 때 root로 시작하는 게 아니라, leaf로 시작한다는 거다.

코드

/**
 * 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 {
    private String ans = "";

    private void traverse(TreeNode node, StringBuilder sb) {
        if (node == null)
            return;

		// StringBuilder 맨 앞에 현재 노드의 값을 추가한다.
        sb.insert(0, (char) (node.val + 'a'));

		// 현재 노드가 leaf 노드인지 체크한다.
        if (node.left == null && node.right == null) {
            String now = sb.toString();
            
            // 사전적으로 가장 작은지 체크한다.
            // compareTo는 기준값이 비교값보다 작으면 -1, 같으면 0, 크면 1을 반환한다.
            if (ans == "" || ans.compareTo(now) > 0)
                ans = now;
            sb.deleteCharAt(0);  // 추가했던 현재 노드의 값을 제거한다.
            return;
        }

		// 자식 노드를 탐색한다.
        traverse(node.left, sb);
        traverse(node.right, sb);

        sb.deleteCharAt(0);  // 추가했던 현재 노드의 값을 제거한다.
    }

    public String smallestFromLeaf(TreeNode root) {
        traverse(root, new StringBuilder());
        return ans;
    }
}

푼 후

• 트리 탐색은 익숙했는데, 문자열 다루는 게 헷갈렸다.
• 모든 노드를 한 번씩 탐색하기 때문에 총 노드 개수를 n이라고 하면 시간 복잡도는 O(n)이다. 공간 복잡도는 재귀 함수의 깊이로 구할 수 있는데, 트리가 한 쪽으로만 길면 노드의 개수만큼 깊이를 갖기 때문에 공간 복잡도는 O(n)이다.