[자바] Leetcode 1302 - Deepest Leaves Sum

leetcode.com/problems/deepest-leaves-sum/

Deepest Leaves Sum - LeetCode

가장 아래에 있는 노드들의 value값을 합하는 문제다. 

'처음부터 너무 많은 생각을 하지 말자!'고 결심하고 정말 떠오르는 대로 문제를 풀었더니 통과는 했는데 애잔한 결과가 나왔다 ㅋㅋㅋ

---

Solution 

나름의 BFS로 가장 아래의 노드가 몇 depth에 있는지 찾고, 다시 한번 Queue를 돌리면서 해당 depth에 속하는 노드들의 val을 더하는 풀이법을 사용했다. 

/**
 * 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 {
    public int deepestLeavesSum(TreeNode root) {
        int depth = 0;

        Queue<Node> que = new LinkedList<>();
        que.add(new Node(root, 0));

        Node tmp;
        TreeNode right_node;
        TreeNode left_node;
        while(!que.isEmpty()){
            tmp = que.poll();
            depth = Math.max(depth, tmp.cnt);

            right_node = tmp.treeNode.right;
            if(right_node !=null) que.add(new Node(right_node,tmp.cnt+1));
            left_node = tmp.treeNode.left;
            if(left_node !=null) que.add(new Node(left_node,tmp.cnt+1));
        }

        //while에서 빠져나온 depth가 가장 깊은 길이
        que.clear();
        que.add(new Node(root, 0));
        int total_sum = 0;
        while(!que.isEmpty()){
            tmp = que.poll();

            if(tmp.cnt==depth) total_sum += tmp.treeNode.val;
            right_node = tmp.treeNode.right;
            if(right_node !=null) que.add(new Node(right_node,tmp.cnt+1));
            left_node = tmp.treeNode.left;
            if(left_node !=null) que.add(new Node(left_node,tmp.cnt+1));

        }


        return total_sum;        
    }
    
    
    public static class Node{
        TreeNode treeNode;
        int cnt;

        public Node(TreeNode treeNode, int cnt){
            this.treeNode = treeNode;
            this.cnt = cnt;
        }
    }    
}

 

 

다른 사람의 Solution 

leetcode.com/problems/deepest-leaves-sum/discuss/463239/JavaC%2B%2BPython-Level-Traversal

[Java/C++/Python] Level Traversal - LeetCode Discuss

ㄱ ㅣ똥차다 정말

마지막 노드인 경우에는 내 right과 left가 모두 null임을 이용하여서 풀었다. 처음 나도 이 방법을 생각했다가 아래의 Node 5와 같이 마지막 노드는 아닌데 자식 노드가 없는 경우도 있는데 어떡하지? 라는 생각에 가장 단순 무식한 방법으로 풀기로 돌린 거였는데 que.size()를 이용하면 됐었던 거였다.

 어차피 root부터 시작하면서 같은 레벨에 있는 노드들은 while문 안에서 같이 que에 들어가게 되어있다. 즉, que.size()로 나오는 값이 같은 레벨에 있는 노드들의 갯수인 것. 그 횟수만큼을 for문으로 돌면서 total_sum에 더해주면 값은 나온다. 아이디어를 참고한 사람의 경우에는, for문에서 아예 res(내 코드로 치면 total_sum)을 0으로 초기화해주던데 와 이것도 나한텐 신박하다. 

/**
 * 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 {
    public int deepestLeavesSum(TreeNode root) {
        int total_sum = 0;

        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()){
            total_sum = 0;
            for(int i= que.size()-1;i>=0;i--){
                TreeNode node = que.poll();
                total_sum += node.val;

                if(node.left!=null) que.add(node.left);
                if(node.right!=null) que.add(node.right);
            }
        }
        return total_sum;   
    }
   
}