오늘 할일
1. 루틴(LeetCode, 토익, 강의, 창엔업무)
2. 인공지능 개론 시험준비
오늘 한일
1. 창엔 공동문서 기입
2. LeetCode
- Longest ZigZag Path in a Binary Tree는 이진트리에서 가장 긴 지그재그 접근 길이를 구하는 것이다. 코드를 작성하여 제출해보았다.
/**
* 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 int max_zigzag_length=0;
private void zigzag_length_left(TreeNode node, int length){
if(node.right!=null){
zigzag_length_right(node.right, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void zigzag_length_right(TreeNode node, int length){
if(node.left!=null){
zigzag_length_left(node.left, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void DFS(TreeNode node){
if (node==null)
return;
if(node.left!=null){
zigzag_length_left(node.left, 1);
DFS(node.left);
}
if(node.right!=null){
zigzag_length_right(node.right, 1);
DFS(node.right);
}
}
public int longestZigZag(TreeNode root) {
if(root==null || (root.left==null && root.right==null))
return 0;
DFS(root);
return max_zigzag_length;
}
}
이 테스트 케이스는 잘못되었다고 생각했었는데 문제 조건을 보니 node.val은 1부터 1000까지가 가능했다. 문제에 정확히 명시되어있지 않지만, 같은 값을 가지는 노드에만 접근이 가능한 것 같다. zigzag재귀 함수에 값을 보내게끔 함수를 변경하자.
/**
* 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 int max_zigzag_length=0;
private void zigzag_length_left(TreeNode node, int length, int node_val){
if(node.val!=node_val)
return;
if(node.right!=null){
zigzag_length_right(node.right, length+1, node_val);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void zigzag_length_right(TreeNode node, int length, int node_val){
if(node.val!=node_val)
return;
if(node.left!=null){
zigzag_length_left(node.left, length+1, node_val);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void DFS(TreeNode node){
if (node==null)
return;
if(node.left!=null){
zigzag_length_left(node.left, 1, node.val);
DFS(node.left);
}
if(node.right!=null){
zigzag_length_right(node.right, 1, node.val);
DFS(node.right);
}
}
public int longestZigZag(TreeNode root) {
if(root==null || (root.left==null && root.right==null))
return 0;
DFS(root);
return max_zigzag_length;
}
}
문제를 잘못 이해한 듯 하다. 아마 노드에 값에 상관없이 지그재그가 가능한 최대길이를 구하는 것으로 추정된다.
실제 다시 실행해본 결과
정답도 맞게 나왔다. 그러나 최대 런타임 제한을 넘겨 fail이 뜬 것으로 보인다.
보다 빠른 탐색을 위해, 탐색 이전에 트리의 깊이를 계산하고 최대 지그재그 값이 트리의 깊이와 같아진다면 추가적인 탐색을 수행하지 않게 적용해보겠다.
/**
* 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 int max_zigzag_length=0;
private int tree_depth;
private void zigzag_length_left(TreeNode node, int length){
if(node.right!=null){
zigzag_length_right(node.right, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void zigzag_length_right(TreeNode node, int length){
if(node.left!=null){
zigzag_length_left(node.left, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void DFS(TreeNode node){
if (node==null)
return;
if(node.left!=null){
zigzag_length_left(node.left, 1);
if(max_zigzag_length==tree_depth-1)
return;
DFS(node.left);
}
if(node.right!=null){
zigzag_length_right(node.right, 1);
if(max_zigzag_length==tree_depth-1)
return;
DFS(node.right);
}
}
public int find_depth(TreeNode root){
if(root==null)
return 0;
return Math.max(1+find_depth(root.left), 1+find_depth(root.right));
}
public int longestZigZag(TreeNode root) {
if(root==null || (root.left==null && root.right==null))
return 0;
tree_depth=find_depth(root);
DFS(root);
return max_zigzag_length;
}
}
속도가 빨라지긴 했지만 전체 테스트를 통과하지 못했다.
그 외에 조건체크의 위치를 옮기며 최적화를 꾀해봤지만 1900대를 왔다갔다하며 전체 테스트를 통과하지는 못했다.
현재 DFS기반 탐색 방법보다 BFS기반 탐색 방법이 훨씬 최상복잡도를 좋게 만들 수 있어보인다.
/**
* 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 int max_zigzag_length=0;
private int tree_depth;
private Queue<TreeNode> queue=new LinkedList();
private void zigzag_length_left(TreeNode node, int length){
if(node.right!=null){
zigzag_length_right(node.right, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void zigzag_length_right(TreeNode node, int length){
if(node.left!=null){
zigzag_length_left(node.left, length+1);
}
if(max_zigzag_length<length)
max_zigzag_length=length;
}
private void DFS(TreeNode node){
if (node==null)
return;
if(max_zigzag_length==tree_depth-1)
return;
if(node.left!=null){
zigzag_length_left(node.left, 1);
DFS(node.left);
}
if(node.right!=null){
zigzag_length_right(node.right, 1);
DFS(node.right);
}
}
private void BFS(TreeNode node){
if(node==null)
return;
queue.add(node);
while(!queue.isEmpty()){
if(max_zigzag_length==tree_depth-1)
return;
TreeNode node_deq=queue.remove();
if(node_deq.left!=null){
queue.add(node_deq.left);
zigzag_length_left(node_deq.left, 1);
}
if(node_deq.right!=null){
queue.add(node_deq.right);
zigzag_length_right(node_deq.right, 1);
}
}
}
public int find_depth(TreeNode root){
if(root==null)
return 0;
return Math.max(1+find_depth(root.left), 1+find_depth(root.right));
}
public int longestZigZag(TreeNode root) {
if(root==null || (root.left==null && root.right==null))
return 0;
tree_depth=find_depth(root);
BFS(root);
return max_zigzag_length;
}
}
하지만 예상과 달리 BFS방식이 더 오랜 시간이 소요되었다. 어떻게 최적화할 수 있을까? 일단 기존의 DFS방식으로 되돌아가겠다.
이제 3학년..