Today I Learned

오늘 할일
1. LeetCode
2. 인프라 강의
3. 세모봉 개발
4. 매일 토익
5. 소웨공 공부
6. 모바일 프로그래밍 과제
7. 알고리즘 과제(하노이, 거꾸로 선택정렬(내림, 오름), 파일출력)

오늘 한일
1. LeetCode

• Path sum III는 트리에 연속되는 합을 구하는 문제이다. 모든 노드를 기준으로 내려가는 경우도 고려하기 위해 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 {
    private int hit_count=1;
    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++;
        DFS(node.left, current_sum);
        DFS(node.right, current_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=1;
    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++;
        DFS(node.left, current_sum);
        DFS(node.right, current_sum);
        DFS(node.left, 0);
        DFS(node.right, 0);
    }

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

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