Today I Leanred

오늘 할일
1. LeetCode
2. 영상처리 과제 마무리
3. 매일 LC /RC 토익
4. 소웨공 발표
5. 세모봉 or 인프라 강의

오늘 한일
1. LeetCode

• 104. Maximum Depth of Binary Tree는 이진 트리의 깊이를 찾는 문제이다. 다만 트리를 잘 몰라 BFS로 구현은 했지만 높이를 어떻게 구해야할지 고민중이다.

public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        if(root.left==null && root.right==null)
            return 1;

        int max=1;
        Stack<TreeNode> stack=new Stack();
        TreeNode iter=root;
        stack.push(root);
        while(!stack.isEmpty()){
            iter=stack.pop();
            System.out.println(iter.val);
            if(iter.left!=null){//깊이가 ++되는 지점
                stack.push(iter.left);
            }
            if(iter.right!=null){
                stack.push(iter.right);
                max++;
            }
        }

        return max;
    }

높이를 구하려면 하나의 깊이를 쭉 찍고(DFS) max값을 갱신하면 될 듯 한네 BFS라 어려워보인다. DFS로 우선 리팩토링해보자.못하겠다. 정말 트리에 대한 지식이 많이 부족한 듯 하다. 마지막으로 재귀로 시도해보자. 이조차도 높이값을 어떻게 처리해야할지 어려워서 결국 검색을 해보았다. 최종적으로 만들어진 코드는 아래와 같다.

/**
 * 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 {
    int answer=0;

    public void findMaxDepth(TreeNode node, int depth){
        if(node==null)
            return;

        if(answer<depth)
            answer=depth;
        
        if(node.left!=null)
            findMaxDepth(node.left, depth+1);
        if(node.right!=null)
            findMaxDepth(node.right, depth+1);
    }

    public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        findMaxDepth(root, 1);
        return answer;
    }
}

최대 높이값을 매 차시마다 공유하기 위해서 클래스 변수를 사용하였다. 높이값을 초기에 1을 건네주면, 각 재귀에서는 인자로 전달받은 depth값으로 각각의 높이 계산을 시작한다. 그러다가 막히면 return되며 작업이 끝나는데 매 노드 iteration시마다 answer와 depth값을 비교하여 항상 answer는 가장 깊은 깊이값을 가질 수 있게 한다. 추가적으로 현재 root노드도 1로 세어 madDepth에서 findMasDepth의 초기 depth값으로 1을 건네주었지만, head로 null값이 들어올 수도 있기 때문에 해당 경우만 예외처리를 하여 0이 반환되게 하였다.

추가적으로 다른 사람들의 코드를 보았는데

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

로 아주 간단하게 구하였다.. 기존의 maxDepth함수 자체를 재귀에 사용하며 인자로 depth값을 전달하지 않고 Math.max()안에서 1씩 더하는 과정에서 호출시켰다..대박이네요..

3. 매일 토익 LC/RC
   
   
   
   선지와 똑같은 단어를 사용하지 않고 유사어를 사용하는 점 유의, 생각보다 앞부분에 마지막 문제의 답이 나온다는 점 유의.