online advertising

Sunday, May 28, 2017

LeetCode OJ - Subtree of Another Tree

Problem:

Please find the problem here.

Analysis:

In this problem, I didn't spend much time to optimize the solution. It is a simple dirty yet $ O(n) $ solution. I simply computed the in-order traversal of both trees, and I claim that if the string representation matches, it must be an identical sub-tree.

Solution:

The key thing that we need to worry about is whether or not a substring match is due to reason other than a complete sub-tree matches, for example, the substring match was due to taking some data in the earlier subtrees or some later subtrees. It is made impossible by adding the brackets. The bracket helped us to make sure in the parent string the substring is properly parenthesized, so it has to be a subtree and a subtree alone. The commas are also important, it make sure we cannot concatenate numbers differently to yield the same string.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/subtree-of-another-tree

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

using namespace std;

namespace _LEET_SUBTREE_OF_ANOTHER_TREE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        void ToString(TreeNode* s, ostringstream& sout)
        {
            if (s == nullptr)
            {
                sout << "#" << ",";
            }
            else
            {
                sout << "(";
                ToString(s->left, sout);
                sout << s->val;
                sout << ",";
                ToString(s->right, sout);
                sout << ")";
            }
        }
        bool isSubtree(TreeNode* s, TreeNode* t)
        {
            ostringstream sout;
            ostringstream tout;
            ToString(s, sout);
            ToString(t, tout);
            string sstr = sout.str();
            string tstr = tout.str();
            const char* x = strstr(sstr.c_str(), tstr.c_str());
            return (x != nullptr);
        }
    };
};

using namespace _LEET_SUBTREE_OF_ANOTHER_TREE;

int LEET_SUBTREE_OF_ANOTHER_TREE()
{
    TreeNode a(3);
    TreeNode b(4);
    TreeNode c(5);
    TreeNode d(1);
    TreeNode e(2);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = nullptr;
    c.right = nullptr;
    d.left = nullptr;
    d.right = nullptr;
    e.left = nullptr;
    e.right = nullptr;

    TreeNode p(4);
    TreeNode q(1);
    TreeNode r(2);
    p.left = &q;
    p.right = &r;
    q.left = nullptr;
    q.right = nullptr;
    r.left = nullptr;
    r.right = nullptr;

    Solution s;
    cout << (s.isSubtree(&a, &p) ? "True" : "False") << endl;
    return 0;
}

No comments :

Post a Comment