리트코드 75 18일 차, 이제 일주일치(21개) 남았는데, 여름휴가를 즐기는 중이다. 비행기, 숙소 예약까지 이미 끝난 거라 마음이 심란하지만 힐링한다고 생각하고 일정대로 가기로 했다. 이 포스팅은 예약 발행될 예정이다. 여행 가기 전에 일주일 치 포스팅을 미리 해놓으면 좋을 텐데, 아마 힘들 것 같다. 😂 이진트리 문제를 3개 풀어봤다.
437. Path Sum III
주어진 이진트리 root와 정수 targetSum이 있을 때, 경로를 따르는 노드 값들의 합이 targetSum이 되는 경로의 수를 구하라. 경로는 시작 또는 끝이 루트 노드이거나 리프 노드일 필요는 없지만 항상 아래 방향(부모 노드에서 자식 노드 방향으로)으로 가야 한다.
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
부모 노드에서 시작하는 경로가 있고, 자식 노드로 내려가면 해당 노드에서부터 시작하는 새로운 경로에서 targetSum을 가지는 경우가 있는지 확인해야 한다. 처음에는 DFS를 이용해서 문제를 풀려고 했는데, 이 경우 정답이 있는 path를 중복해서 방문한다. 예를 들어 [1, 2, 4, 8] 트리가 있으면 1에서 시작하는 경로를 시작하고 자식노드 2로 내려갔을 때 새로운 경로, 그 다음 노드 4에서 시작하는 경로를 찾는다. 그런데 2에서 경로를 시작한 경우도 노드 4에서 시작하는 경로를 찾는다. 그래서 정답보다 많은 수의 경로가 나왔다. 중복으로 방문하는 경로를 저장하고 확인하는 방법이 있겠지만, BFS를 구현해서 각 노드에서 시작하는 경로를 한 번씩만 도는 것이 더 수월했다.
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
int[] ret = new int[1];
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
TreeNode node = q.poll();
pathSum(node, targetSum, 0, ret);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
return ret[0];
}
private void pathSum(TreeNode node, int targetSum, long cur, int[] ret) {
if (node == null) {
return;
}
long val = node.val + cur;
if (val == targetSum) {
ret[0]++;
}
pathSum(node.left, targetSum, val, ret);
pathSum(node.right, targetSum, val, ret);
}
}이진트리의 노드 개수를 n개라고 했을 때, pathSum은 자식노드에 대해 재귀적으로 실행되는 것을 제외하고 각 노드에 대해서 한 번씩 수행한다. 그리고 root 노드에서 시작한 pathSum은 전체 노드를 순회한다. 그래서 시간 복잡도는 O(n^2)가 된다. 공간 복잡도는 큐에 들어가는 노드의 수, 그리고 재귀 함수가 호출되는 깊이로 계산할 수 있을 것이다. 큐에 들어갈 수 있는 최대 노드의 수는 1/2 * 2^(logn) -1 = n/2 -1이고, 재귀 함수는 트리의 높이만큼 호출될 수 있으므로 logn이 된다. 그래서 O(n/2 -1 + logn)인데 가장 높은 인자만 고려하므로 공간 복잡도는 O(n)이 된다.
236. Lowest Common Ancestor of a Binary Tree
이진트리에서 주어진 노드 p와 q의 lowest common ancestor(LCA)를 찾아라. 노드는 자기 자신의 자식 노드가 될 수 있다.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
주어진 노드 p, q가 모두 루트 노드의 왼쪽에 있다면 LCA는 root.left가 되거나 더 아래에 있을 수 있다. 반대로 루트 노드의 오른쪽에 있다면 LCA는 root.right가 되거나 더 아래에 있을 수 있다. 이 두 경우는 LCA를 찾기 위해 더 아래로 탐색이 필요한 경우다.
현재의 root가 LCA가 되는 경우는 p, q가 서로 다른 자식 노드인 경우 또는 root가 p 또는 q인 경우가 되겠다. 이 조건을 재귀적으로 확인해서 문제를 풀 수 있다.
내가 구현한 방법의 경우 노드를 한 뎁스 내려갈 때마다 search를 하고 있다. 중복되는 연산이 있고 내가 제출한 솔루션이 남들보다 많이 느렸기 때문에 더 좋은 솔루션이 있는 것 같아서 추가로 업데이트를 할 예정이다.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val == p.val || root.val == q.val) {
return root;
}
if (search(root.left, p) && search(root.left, q)) {
return lowestCommonAncestor(root.left, p, q);
} else if (search(root.right, p) && search(root.right, q)) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
private boolean search(TreeNode root, TreeNode target) {
if (root == null) {
return false;
}
if (root.val == target.val) {
return true;
}
if (root.left != null && search(root.left, target)) {
return true;
}
if (root.right != null && search(root.right, target)) {
return true;
}
return false;
}
}
1372. Longest ZigZag Path in a Binary Tree
이진트리의 root가 주어졌을 때 이 이진트리에서 가장 긴 지그재그 경로의 길이를 리턴하라. 지그재그 경로의 정의는 다음과 같다:
이진트리 내에서 노드를 선택하고 방향을 오른쪽 또는 왼쪽으로 정한다. 현재 방향이 오른쪽이라면 현재 노드의 오른쪽 자식 노드로 이동하고 왼쪽이라면 왼쪽 자식 노드로 이동한다. 방향을 오른쪽에서 왼쪽, 또는 왼쪽에서 오른쪽으로 변경한다. 더 이상 트리에서 이동할 수 없을 때까지 반복한다. 지그재그 경로의 길이는 방문한 노드의 개수 -1이다. (단일 노드는 길이가 0)
You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follow:
Choose any node in the binary tree and a direction (right or left). If the current direction is right, move to the right child of the current node; otherwise, move to the left child.Change the direction from right to left or from left to right.Repeat the second and third steps until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.
root 노드에서 양방향 모두 경로 탐색을 시작한다. 그리고 자식 노드로 내려가면서 자식 노드를 기준으로 하는 새로운 경로를 함께 탐색한다. 새로 시작하는 경로의 경우 부모 노드에서 시작한 경로와 같은 방향으로 출발하면 길이가 항상 1보다 작고 중복된 경로이므로 탐색할 필요가 없다. 그래서 새로 시작하는 경로는 기존 경로와는 다른 방향 경로만 탐색하면 된다.
class Solution {
public int longestZigZag(TreeNode root) {
int[] ret = new int[1];
visit(root, true, 0, ret);
visit(root, false, 0, ret);
return ret[0];
}
private void visit(TreeNode node, boolean isLeft, int edge, int[] ret) {
if (node == null) {
return;
}
ret[0] = Math.max(ret[0], edge);
if (isLeft) {
visit(node.left, false, edge+1, ret);
visit(node.right, true, 1, ret);
}
if (!isLeft) {
visit(node.right, true, edge+1, ret);
visit(node.left, false, 1, ret);
}
}
}자식 노드에서 새로운 경로를 탐색할 때 기존 방향과 반대로 가기 때문에 중복해서 노드를 방문하는 경우는 없을 것이라 시간복잡도는 O(n)이 된다. 공간 복잡도는 재귀 호출을 위한 스택 공간이 최악의 경우 n보다 많을 수 없어서 O(n)이 된다.
