Leet Code - 112. Path Sum(C++)

예제: 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.

Note:
A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,

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

풀이

문제 자체는 크게 어렵지 않았지만, 문제를 정확히 읽지 않으면 헤맬 수 있는 문제이다.(영어가 문제인가..)

답은 'root-to-leaf' 라는 점에 유의하자.

필자는 재귀함수를 사용하여 노드를 타고 내려가면서, leaf까지 합을 더한 후 sum과 비교하여 true/false를 반환하였다.

전체적인 소스코드는 아래와 같다.

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	bool hasPathSum(TreeNode* root, int sum) {
		return solve(root, 0, sum);
	}

	bool solve(TreeNode* node, int acc, int sum) {
		if (node == NULL) return false;

		int nextAcc = acc + node->val;

		if (node->left == NULL && node->right == NULL) {
			return nextAcc == sum;
		}


		return solve(node->left, nextAcc, sum) || solve(node->right, nextAcc, sum);
	}
};

풀이 후기

필자는 요즘 운동을 시작했는데, 야근에 운동까지 해서 그런지 머리가 안돌아간다.
문제만 정확히 이해하면 쉽게 풀 수 있었는데 삽질을 해버렸다.
운동을 하고 야식을 시켜놓고 이런 글을 쓰는걸 보니, 나는 건강한 돼지가 되고 싶은 모양이다.🐷