[OJ.leetcode] Path Sum

https://oj.leetcode.com/problems/path-sum/

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

 

 /*

 DFS로 쉽게 풀수있다

 시간복잡도 : O(n)

 

 조금 헤맨이유: 중간까지의 합이 아니라 left node까지 모두 더한 값이 sum과 같아야 true인데 착각함. 

edge case:

 {1,2} 1 => false; left leaf node가 존재하므로. 1->2 != 1 이므로 false

 {1} 1 => true; 

 

test case

 {1} 0

 {1} 1

 {0,1} 1

 {0,1} 0

 {1,2,3,4} 7

 

배운것 : recursive와 전역변수는 좋은 궁합이 아니다. 전역변수를 사용하여 매 call마다 값을 비교할 경우,콜스택을 타고 내려갔다 올라올때마다   전역변수를 더했다가 다시 빼줘야하는 번거로움이 있다. 그냥 함수를 하나 재정의해서 쓰던지, 인자로 값을 넘겨주는것이 코드 복잡도를 줄일 수 있는 방법임. 

이번 문제의 경우 '핵심' 은 매 call마다 node의 값을 더해서 sum과 비교하는 것이 아니라(처음에  이렇게 짬) sum에서 매 call마다 node의 값을 빼면서 접근한다면 문제의 복잡도를 훨씬 줄일 수 있다.

 */

 

class Solution {

public:

    bool hasPathSum(TreeNode *root, int sum) {

        if(root == NULL) return false;

        

        sum -= root->val;

        

        if(!root->left && !root->right) {

            if(sum == 0) return true;

            else {

                return false;

            }

        }

        

        return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);

    }

};