99클럽 코테 스터디 13일차 TIL + 또또 DFS

1. What I learn?

dfs문제… 저번에도 풀었지만 이번에도 여전히 헷갈렸던 문제이다.

2. What I did?

재귀를 활용해서 문제를 풀었어야만 했고 그걸 알고있었지만 어떻게 해야할지는 감이 오지 않았다.

우선LeetCode에서 사용하는 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;
 *     }
 * }
 */

.val을 통해서 값에 접근할 수 있다.

left를 통해서 현재 노드기준 left가지로 향한다.

right를 통해서 현재 노드기준 right가지로 향한다.

3. How did I solve?

class Solution {
    int sum=0;
    int maxHeight = Integer.MIN_VALUE;
    int height =0;
    public void dfs(TreeNode root,int height){
        if(root == null)return;
        height +=1;

        if(root.left == null && root.right == null){
            if(maxHeight <height){
                maxHeight = height;
                sum = root.val;
            }
            else if(maxHeight == height){
                sum +=root.val;
            }
        }

        dfs(root.right, height);
        dfs(root.left, height);

    }
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, height);
        return sum;
    }

}

재귀를 빠져나오는 조건의 식은 TreeNode의 값이 null일때 즉 더이상 탐색할 수 없는 노드가 존재하는 경우이다.

이제 다시 코드를 봐보자

class Solution {
    int sum=0;
    int maxHeight = Integer.MIN_VALUE;
    int height =0;
    public void dfs(TreeNode root,int height){
        //node의 값이 null인경우 즉 재귀를 빠져나오는 경우이다.
       
        if(root == null)return;
        //null이 아니면 현재 노드의 깊이에 +1을 수행한다.
        height +=1;

				//왼쪽, 오른쪽 가지의 node가 null인 경우 == 마지막 노드에 도달한 경우
        if(root.left == null && root.right == null){
		        // maxHeight  < height 인 경우는 딱 1회 
		        //첫 깊이 탐색을 마친 상태이다. 
            if(maxHeight <height){
		            //maxheight를 현재 height로 지정한다.
		            //이는 가장 깊은 노드를 의미한다.
                maxHeight = height;
                //가장 깊은 노드의 값을 찾았으니 root.val의 값을 sum에 넣어준다.
                sum = root.val;
            }
	          //또 다른 가지에서 같은 깊이에 있는 노드를 발견하는 경우이다. 
            else if(maxHeight == height){
		            //sum값에 해당 노드의 값을 더한다.
                sum +=root.val;
            }
        }

				//가장 깊은 노드가 아닌 경우에는 탐색을 계속 수행한다.
        dfs(root.right, height);
        dfs(root.left, height);

    }
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, height);
        return sum;
    }

}

4. Review

며칠전에 풀었던 문제임에도 불구하고 또 까먹어서 도움을 받아버린 문제이다. 잊지않고 기억하지 않도록 같은 유형의 문제를 자주 만나거나 이전에 풀었던 문제를 풀어야할 것 같다.

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL