[LeetCode] 404. Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/description/

Leetcode - Sum of Left Leaves

문제 유형 : 이진 트리, dfs, 재귀

문제 난이도 : Easy

 

문제

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

 

이진 트리의 루트가 주어진다. 모든 왼쪽 잎 노드의 값의 합을 구하시오.

잎 노드란 자식 노드가 없는 노드를 말합니다.

 

풀이

말 그대로 이진트리를 순회하면서 왼쪽 리프노드의 합을 반환하면 된다.

현재 왼쪽 자식 노드가 리프노드인지 체크하고, 맞다면 값을 가져온다. 왼쪽 서브트리와 오른쪽 서브트리의 값들과 합쳐서 반환한다.

이를 재귀적으로 순회하면 답이 나온다.

 

이 외에도 순회하면서 값을 누적하는 방법은 너무나 많다.

 

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL) return 0;

        int sum = 0;
        if(root -> left != NULL && root -> left -> left == NULL && root -> left -> right == NULL) sum = root -> left -> val;

        return sum + sumOfLeftLeaves(root -> left) + sumOfLeftLeaves(root -> right);
    }
};