Path Sum - LeetCode

Problem

1. input: 이진 트리의 루트 노드 root, 정수 targetSum
2. output: 트리의 루트노드부터 임의의 리프노드로 가는 경로의 모든 노드의 합이 targetSum이 되는 경우 T/F 리턴
   • The number of nodes in the tree is in the range [0, 5000].
   • 1000 <= Node.val <= 1000
   • 1000 <= targetSum <= 1000

Idea

루트노드를 시작으로 DFS 탐색으로 리프노드에 도달할 때까지 경로의 노드들의 값을 더해주면 된다 → Sol1

Solution

1. DFS

   루트노드 → 리프노드 경로의 모든 노드들의 값 더해서 targetSum이 되는지 확인

   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       fun hasPathSum(root: TreeNode?, targetSum: Int, sum: Int = 0): Boolean {
           if (root == null) return false
           val left = if (root!!.left != null) hasPathSum(root!!.left, targetSum, sum + root!!.`val`) else false
           val right = if (root!!.right != null) hasPathSum(root!!.right, targetSum, sum + root!!.`val`) else false
           if (root!!.left == null && root!!.right == null && sum + root!!.`val` == targetSum) return true 
           return left || right
       }
   }
   

   시간 복잡도: 트리 탐색 = n

   

Point