리트코드 75 16일 차. 이진트리 1문제, BST 1문제, 백트래킹 1문제를 풀었다. 벌써 2주가 지났다. 48문제를 푼 건데 남은 27문제는 혼자서는 도저히 안 풀릴 것 같은 문제들이다 😢 각 잡고 30분 동안 풀어보고, 못 풀면 해답 보고 풀이를 이해하는 식으로 공부해보려고 한다.
1161. Maximum Level Sum of a Binary Tree
주어진 이진 트리에서 루트를 레벨 1, 그다음 자식 노드들을 레벨 2, 3...으로 정의할 때 각 레벨의 모든 노드 값의 합이 최대가 되는 가장 작은 레벨을 구하라.
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.
Level order traversal을 구현해서 해당 레벨의 모든 노드의 합을 구하고 max를 업데이트한다.
class Solution {
public int maxLevelSum(TreeNode root) {
int level=1, maxSum=Integer.MIN_VALUE, maxLevel=1;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
int size = q.size();
int sum=0;
for(int i=0; i<size; i++) {
TreeNode node = q.poll();
sum += node.val;
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
if (maxSum < sum) {
maxSum = sum;
maxLevel = level;
}
level++;
}
return maxLevel;
}
}이진트리의 모든 노드를 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 큐에 들어가는 노드의 개수를 통해 계산해 볼 수 있다. 트리의 레벨(깊이)이 logn일 때 큐에서 가장 많은 노드를 저장할 것이다. 해당 레벨에서 가질 수 있는 최대 노드의 개수는 2^(logn)=n 이기 때문에 O(n)이 된다.
450. Delete Node in a BST
이진 검색 트리에서 값이 key인 노드를 찾아서 삭제한다.
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.If the node is found, delete the node.
BST에서 노드를 삭제하는 방법이 기억이 안 나서 구글링을 하고 문제를 풀었다. key 값이 없는 경우는 그냥 트리 그대로 리턴할 수 있지만 key값이 있는 경우 삭제할 때 케이스는 세 가지로 분류할 수 있다.
첫 번째는 자식 노드가 없는 경우. 이 경우는 해당 노드의 레퍼런스를 트리에서 없애면 된다.
두 번째는 자식 노드가 하나만 있는 경우다. 이 경우도 간단히 해당 노드 대신에 자식 노드로 연결을 바꾸기만 하면 된다.
세 번째로 자식 노드가 두 개인 경우가 까다롭다. 이 경우 BST 조건을 지키면서 값을 바꿔줘야 한다. 오른쪽 자식 노드에서 가장 작은 값(minimum right value)을 찾는다. 이 값을 삭제할 노드 자리에 바꿔주고, 그 노드를 삭제한다.
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return root;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
} else if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else { // find minimum right value
TreeNode node = root.right;
while(node.left != null) {
node = node.left;
}
root.val = node.val;
root.right = deleteNode(root.right, node.val);
}
} else {
if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
root.left = deleteNode(root.left, key);
}
}
return root;
}
}균형 잡힌 BST라면 노드를 찾는데에 O(logn)이 걸리고, 최악의 경우 (Skewed) O(n)이 걸릴 수 있다. 공간 복잡도는 함수가 트리의 높이만큼 재귀적으로 들어가기 때문에 마찬가지로 균형잡힌 BST는 O(logn), 최악의 경우 O(n)이 필요하다.
17. Letter Combinations of a Phone Number
주어진 digits로 가능한 모든 문자열 조합을 찾아서 리턴하라.
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
letters 배열에 주어진 숫자에서 나올 수 있는 문자열 조합을 저장해 둔다. 그리고 숫자마다 문자열을 돌면서 조합을 stringbuilder에 추가하고 digits의 길이가 되면 리스트에 추가한다.
class Solution {
private String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) {
return result;
}
dfs(result, digits, new StringBuilder(), 0);
return result;
}
private void dfs(List<String> result, String digits, StringBuilder sb, int curIdx) {
if (sb.length() == digits.length()) {
result.add(sb.toString());
return;
}
char curChar = digits.charAt(curIdx);
String comb = letters[curChar-'0'];
for(int i=0; i<comb.length(); i++) {
sb.append(comb.charAt(i));
dfs(result, digits, sb, curIdx+1);
sb.deleteCharAt(sb.length()-1);
}
}
}digits의 길이를 n이라고 할 때, 시간 복잡도는 O(4^n), 문자열 조합을 저장하는 리스트를 제외하고 공간 복잡도는 재귀 호출 크기만큼 필요하기 때문에 O(n)이 된다.
