Today I Learned

오늘 할일
1. LeetCode
2. 창엔 2일차
3. 매일 토익 LC/RC
4. 인프라 강의듣기

오늘 한일
1. LeetCode

• 437. Path Sum III는 DFS탐색하여 부모->자식 연속노드의 합이 특정 target_sum이 되는 개수를 리턴하는 문제이다. 초기 코드는 아래와 같다.

/**
 * 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 {
    private int hit_count=0;
    private int target_sum;

    private void DFS(TreeNode node, int current_sum){
        if(node==null){
            return;
        }

        current_sum+=node.val;
        if(current_sum==target_sum)
            this.hit_count++;
        if(node.left!=null){
            DFS(node.left, current_sum);
        }
        if(node. right!=null){
            DFS(node.right, current_sum);
        }
    }

    public int pathSum(TreeNode root, int targetSum) {
        this.target_sum=targetSum;
        this.DFS(root, 0);
        return this.hit_count;
    }
}

문제는 현재는 root노드부터 시작하는 경우만 판단한다. root외에도 그 하위 노드들에서 부터 시작했을 때 target_sum에 해당하는 경우도 헤아려야하는데 그 부분을 어떻게하면 가장 간단하게 해결할 수 있을까? 바로 생각난건 Queue기는 하다.
하지만 현재 필요한 것을 Tree노드부터 현재 말단 node에 이르기까지의 노드들을 앞에서부터 빼며 합을 계산하면 된다.

그래서 queue를 적용한 코드가 아래와 같다.

class Solution {
    private int hit_count=0;
    private int target_sum;
    private Queue<Integer> queue=new LinkedList();

    private void DFS(TreeNode node, int current_sum){
        System.out.println(queue);
        if(node==null){
            while(!queue.isEmpty()){
                if(queue.stream().reduce((prev, curr)->{return prev+curr;}).get()==target_sum)
                    hit_count++;
                queue.remove();
            }
            return;
        }
        queue.add(node.val);
        current_sum+=node.val;
        if(current_sum==target_sum)
            this.hit_count++;
        DFS(node.left, current_sum);
        DFS(node.right, current_sum);
    }

    public int pathSum(TreeNode root, int targetSum) {
        this.target_sum=targetSum;
        this.DFS(root, 0);
        return this.hit_count;
    }
}

다만 이 코드는 queue가 1회만 제대로 작동하고 2회부터는 queue가 통채로 비어있는 상태에서 하위 노드 연산이 들어가 한계가 있을 것이다.

어떻게하면 보다 효율적으로 문제를 해결할 수 있을까? 문제 자체는 굉장히 간단해보이는데 말이다.