online advertising

Sunday, May 28, 2017

LeetCode OJ - Subtree of Another Tree


Please find the problem here.


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.


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.


#include "stdafx.h"


#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

    struct TreeNode
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    class Solution
        void ToString(TreeNode* s, ostringstream& sout)
            if (s == nullptr)
                sout << "#" << ",";
                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);


    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