Thursday, October 27, 2016

LeetCode OJ - Sum of Left Leaves

Problem:

Please find the problem here.

Analysis:

To know if a leaf is a left leaf, I need to know its parent, which I don't if I implemented a basic recursive procedure.

Solution:

I am sure there are many solution to this, but a really simple one is to account for the left leaf value at the parent level, that avoid needing passing one more parameter, and therefore, a helper function.

Code:

#include "stdafx.h"

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

#include "LEET_SUM_OF_LEFT_LEAVES.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SUM_OF_LEFT_LEAVES
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL)
        {
        }
    };
    class Solution
    {
    public:
        int sumOfLeftLeaves(TreeNode* root)
        {
            int sum = 0;
            if (root != nullptr)
            {
                if (root->left != nullptr)
                {
                    if (root->left->left == nullptr && root->left->right == nullptr)
                    {
                        sum += root->left->val;
                    }
                }
                sum += sumOfLeftLeaves(root->left);
                sum += sumOfLeftLeaves(root->right);
            }
            return sum;
        }
    };
};

using namespace _LEET_SUM_OF_LEFT_LEAVES;

int LEET_SUM_OF_LEFT_LEAVES()
{
    Solution solution;
    TreeNode a(3);
    TreeNode b(9);
    TreeNode c(20);
    TreeNode d(15);
    TreeNode e(7);
    a.left = &b;
    a.right = &c;
    c.left = &d;
    c.right = &e;
    cout << solution.sumOfLeftLeaves(&a) << endl;
    return 0;
}

No comments :

Post a Comment