[LeetCode] Path Sum

링크

leetcode.com/problems/path-sum/

Path Sum - LeetCode

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.

 

Constraints:

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

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output: true

 

Example 2:

Input: root = [1,2,3], targetSum = 5

Output: false

 

Example 3:

Input: root = [1,2], targetSum = 0

Output: false

 

 

이진 트리의 루트와 정수 targetSum이 주어지면 트리에 루트에서 리프 경로가 있는 경우 경로를 따라 모든 값을 더하는 것이 targetSum과 같으면 true를 반환합니다. 리프는 자식이없는 노드입니다.

 

조건

• 트리의 노드는 [0, 5000]의 범위를 갖습니다.
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

---

1차시도 -> 

/**
 * 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 static int sumValue = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 자식이 없는 노드까지 가서 되돌아가면서 합산
        // Example 1에서 왜 7이아닌 2가 되었는가?
        // 어떻게 우선 내려가고 나중에 합산할 것인가?
        // 조건은 무엇을 주어야 하는가
        /*
        sudo
        if (root.left == null && root.right == null)
        	then sumValue = sumValue + root.val
            then upToRoot
        */
        
        
        if(root.left != null && root.right != null)
        {
            hasPathSum(root.left, targetSum);
        }
        else if(root.left != null && root.right == null)
        {
            System.out.println("has left : "+root.val);
            hasPathSum(root.left, targetSum);
        }
        else if(root.left == null && root.right != null)
        {
            System.out.println("has right : "+root.val);
            hasPathSum(root.right, targetSum);
        }
        else if(root.left == null && root.right == null)
        {
            sumValue = sumValue + root.val;
            hasPathSum(root, targetSum);
        }
        
        
        if(sumValue == targetSum)
        {
            System.out.println("sumValue :"+  sumValue + " targetSum :" + targetSum);
            return true;
        }
        else 
        {
            System.out.println("sumValue :"+ sumValue + " targetSum :" + targetSum);
            return false;
        }
    }
}

두번째 시도- 좌측 최하단과 우측 최하단까지는 가는거 같은데 leaf path가 왜 저렇게 되는지 아직도 모르겠다.

class Solution {
    public static int sumValue = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        
        /*
        if(no children) => add result
        
        then compare targetSum result
        */
        if(!(root.left == null && root.right == null))
        {
            if(root.left != null && root.right != null)
            {
                hasPathSum(root.left, targetSum);
                hasPathSum(root.right, targetSum);
            }
            else if(root.left != null && root.right == null)
            {
                System.out.println("has left : "+root.val);
                hasPathSum(root.left, targetSum);
            }
            else if(root.left == null && root.right != null)
            {
                System.out.println("has right : "+root.val);
                hasPathSum(root.right, targetSum);
            }
        }
        else
        {
            sumValue = sumValue + root.val;
        }
        
        
        
        if(sumValue == targetSum)
        {
            System.out.println(sumValue);
            return true;
        }
        else 
        {
            System.out.println(sumValue);
            return false;
        }
    }
}

 

오늘은 포기입니다. ㅠㅠ

---

Discuss참조

 

Recursive

 public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.val == targetSum && root.left == null && root.right == null) return true;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

널 -> false
현재 루트의 val이 targetSum과 같고 root.left가 널이며 root의 right가 null이면 true // 그야말로 조건
or 리턴도 되는구나...

---

DFS

class Solution {
    private boolean answer = false;
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        dfs(root,sum,0);
        return answer;    
    }
    
    private void dfs(TreeNode node, int sum, int currentSum){
        if(answer==true) return;
        
        if(node.left==null && node.right==null){
            currentSum+=node.val;
            if(sum==currentSum) answer = true;
            return;
        }
        
        currentSum+=node.val;
        if(node.left!=null) dfs(node.left, sum, currentSum);
        if(node.right!=null) dfs(node.right,sum,currentSum);
    }
}

null -> false
조건은 비스무리 하게 간 것 같지만 메서드를 따로 빼서 할 생각을 못했다.. 그래도 오래걸렸을것 같다.