99클럽 코테 스터디 11일차 TIL, DFS,BFS(Deepest Leaves Sum)

1. 문제 정의

2. 문제 접근

 

dfs를 이용하여 완전탐색을 해주면 될 것 같다.

3. 문제 풀이

1. dfs를 통해 리프 노드까지 이동한다.
2. 리프노드가 maxDepth일 경우 sum을 갱신해주고, 다음 maxDepth의 경우에는 sum 에 값을 더해준다.

4. 코드

/**
 * 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 maxDepth = 0;
    int sum = 0;
    public int deepestLeavesSum(TreeNode root) {
        // calMaxDepth(root,0);
        dfs(root,0);
        return sum;
    }

    //  private void calMaxDepth(TreeNode root, int depth){
    //      if(root == null) return;
    //     if(root.left == null && root.right == null) {
    //         maxDepth = Math.max(maxDepth, depth);
    //     }
    //     calMaxDepth(root.left, depth+1);
    //     calMaxDepth(root.right, depth+1);
    //  }

    private void dfs(TreeNode root, int depth){
        if(root == null) return;

        if(depth > maxDepth){
            maxDepth = depth;
            sum = root.val;
        } else if(maxDepth == depth && root.left == null && root.right == null) {
            sum += root.val;
        }
        // if(root.left == null && root.right == null) {
        //     // maxDepth = Math.max(maxDepth, depth);
        //     if(maxDepth <= depth){
        //         System.out.println(depth);
        //         System.out.println(root.val);
        //         sum += root.val;
        //     }
        // }
        dfs(root.left, depth+1);
        dfs(root.right, depth+1);

    }
}

5. 회고

처음에는 무조건 리프노드이면 된다는 생각으로 풀었다. 그러자 이게 제일 마지막 깊이의 리프노드인지 판별이 되지를 않았다... 그래서 마지막 깊이의 리프노드인지를 판별을 먼저 한후에, 마지막 깊이의 리프노드들의 합을 구해줬더니 해결이 되었다.