Today I Learned

오늘 할일
1. LeetCode
2. 영상처리 과제
3. 세모봉 개발?
4. 영상처리 공부
5. 모바일 프로그래밍 과제
6. 알고리즘 과제

오늘 한일
1. LeetCode

• 1372. Longest ZigZag Path in a Binary Tree은 지그재그 그래프의 최대길이를 구하는 것인데 TLE가 발생하여 실패하였다. 시간을 줄이기 위해 DFS의 조건으로 max_zigzag_length==tree_depth-1에서 아래와 같이 바꾸었다. 이 문제에서 루트노드도 깊이에 포함하고, 지그재그에서 edge의 개수만 세기에 기존의 tree_depth에 2를 뺀 값이 지그재그의 최댓값이라는 판단을 한 것이다.
        
        
        가장 높은 효율을 보여준 코드는 아래와 같다.

class Solution {
    int pathLength = 0;
    public int longestZigZag(TreeNode root) {
        if (root == null) return 0;
        dfs(root, 0, 0);
        return pathLength;
    }
    public void dfs(TreeNode root, int left, int right){
        if (root == null) return;
        pathLength = Math.max( pathLength, Math.max(left, right));
        if (root.left != null) dfs(root.left, right+1, 0);
        if (root.right != null) dfs(root.right, 0, left+1);

    }
}

나는 DFS를 진행하며 모든 노드에서부터 지그재그를 돌린 반면, 위 코드는 DFS를 수행하는 과정에서 지그재그의 깊이를 찾을 수 있게끔 하였다. pathLenfth라는 공유변수에 max값을 담으며 잦은 갱신이 발생하더라도(DFS의 탐색과정마다) 별도의 처리를 하는 시간보다 빠를 것이라는 판단으로 보인다. DFS(root, 0, 0)으로 시작하여 pathLength, left, right의 최댓값으로 pathLength를 갱신한다.
그 후 left가 notnull인 경우 dfs(left, right+1, 0)으로 하여 right에서 받은 길이값을 left로 넣어 늘리는 신기한 사고방식으로 해결하였다. 잘 이해가 되지 않지만 DFS를 진행하며 처리하는 방식에 대하여 최대한 생각해보는 것 정도가 내가 할 수 있는 최선으로 보인다.

• 236. Lowest Common Ancestor of a Binary Tree는 인수로 주어진 p와 q의 최저 공통 조상(Lowest Common Ancestor, LCA)를 찾는 문제이다. 간단하게 queue를 사용하여 DFS에 진행중인 모든 노드쌍(위->아래)를 담고, 둘이 포함되는 경우에 최저 공통 조상을 찾고 리턴하면 될 듯 하다. 아니면 다른 방법이 있을까? prev로 LCA를 가정하고, p나 q가 나올 경우 다른 하나를 찾을 때 까지 기다리다 존재하면 prev를 리턴하면 되지 않을까?

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode p, q;
    private TreeNode result;
    private TreeNode LCA;
    private Boolean is_lca_p_or_q=false;
    private void DFS(TreeNode node, TreeNode prev, int found_pair_count){
        if(node==null && found_pair_count!=2){
            this.LCA=null;
            return;
        }
        if(found_pair_count==2)
            return;
        if((node.equals(p) || node.equals(q)) && found_pair_count==1){
            found_pair_count++;
        }
        if((node.equals(p) || node.equals(q)) && found_pair_count==0){
            found_pair_count++;
            this.LCA=prev;
        }

        if(node.left!=null){
            DFS(node.left, node, found_pair_count);
        }
        if(node.right!=null){
            DFS(node.right, node, found_pair_count);
        }
    }
    private void DFS2(TreeNode node, TreeNode target){
        if(node==null)
            return;
        if(node==target){
            this.is_lca_p_or_q=true;
            return;
        }
        
        if(node.left!=null){
            DFS2(node.left, target);
        }
        if(node.right!=null){
            DFS2(node.right, target);
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p=p;
        this.q=q;
        this.DFS(root, root, 0);
        if(LCA.left==p || LCA.right==p){
            DFS2(p, q);
        } else if(LCA.left==q || LCA.right==q){
            DFS2(q, p);
        }
        if(is_lca_p_or_q){
            if(LCA.left==p || LCA.right==p){
                LCA=p;
            } else if(LCA.left==q || LCA.right==q){
                LCA=q;
            }
        }

        return this.LCA==null?root:this.LCA;
    }
}

더럽지만 코드를 작성해보았을 때 22까지의 테스트를 통과했다. 추가적으로 다뤄야 하는 부분은 P가 Q아래에 있거나 Q가 P아래에 있어서 LCA가 P나 Q가 되는 경우이다.