online advertising

Tuesday, October 28, 2014

LeetCode OJ - sum root to leaf numbers

Problem:

Please find the problem here.

Solution:

Notice only the leaves contribute to the sum, but in the leaves we need to know the whole path, so that's what we will do. In the recursion call, we tell the children the current 'context' (i.e. the number representing its parent path), and at the leaf, we use the context and contribute to the sum, and when the recursive call rewinds, compute the sum.

Code:

#include "stdafx.h"

// https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

#include "LEET_SUM_ROOT_TO_LEAF_NUMBER.h"
#include <map>
#include <iostream>

using namespace std;

namespace _LEET_SUM_ROOT_TO_LEAF_NUMBER
{
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

    class Solution {
    private:
        int sumNumbers(int context, TreeNode *root)
        {
            int result = 0;
            bool is_leaf = true;
            if (root->left != NULL)
            {
                is_leaf = false;
                result += sumNumbers((context + root->val) * 10 , root->left);
            }
            if (root->right != NULL)
            {
                is_leaf = false;
                result += sumNumbers((context + root->val) * 10, root->right);
            }
            if (is_leaf)
            {
                result += (context + root->val);
            }
            return result;
        }
    public:
        int sumNumbers(TreeNode *root)
        {
            if (root == NULL)
            {
                return 0;
            }
            else
            {
                return this->sumNumbers(0, root);
            }
        }
    };

};

using namespace _LEET_SUM_ROOT_TO_LEAF_NUMBER;

int LEET_SUM_ROOT_TO_LEAF_NUMBER()
{   
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    boot->left = root;
    Solution solution;
    cout << solution.sumNumbers(root) << endl;
    return 0;
}

No comments :

Post a Comment