[LeetCode ] 112. Path Sum - 문제풀이

Description

주어진 이진트리를 root부터 leaf 노드까지 탐색하여 targetSum과 일치하는 값이 있는지 찾아가는 문제입니다.

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 100-1000 <= targetSum <= 1000

Solution 1. DFS - Recurtion(재귀)

public boolean hasPathSum(TreeNode root, int targetSum) {
    // 1. recursion - DFS
    if(root == null) return false;
    if(root.left == null && root.right == null) return targetSum - root.val == 0 ; // leaf node
    return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}

깊이우선탐색(DFS) 탐색으로 재귀호출 하며 targetSum에 노드의 값을 빼나가며 leaf node에 도달했을때 0이 나오는 케이스가 있다면 true를 반환하여 최종 true를 내보냅니다.

Solution 2. BFS - Iteration(반복)

public boolean hasPathSum(TreeNode root, int targetSum) {
    // 2. Iteration - BFS
    if(root == null) return false;
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> n = new LinkedList<>();
    q.offer(root);
    n.offer(root.val);
    while(!q.isEmpty()){
        TreeNode cur = q.poll();
        Integer sum = n.poll();
        if(cur.left == null && cur.right==null) { // leaf node
            if(sum == targetSum) return true;
        }
        if(cur.left != null){
            q.offer(cur.left);
            n.offer(cur.left.val + sum);
        }
        if(cur.right != null){
            q.offer(cur.right);
            n.offer(cur.right.val + sum);
        }
    }
    return false;
}

너비우선탐색(BFS)으로 큐를 이용하여 누적 합계값을 저장해가며 노드의 끝까지 탐색해나갑니다. leaf node에 다달했을때 현재 까지 path의 sum을 체크하여 targetSum과 일치할 경우 true를 반환해줍니다.

Reference

Path Sum - LeetCode

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,