C++ straight forward solution


  • 0
    D

    Two extra functions to solve this problem
    void find_node() : find all nodes whose value are equal to the root of t.
    bool is_subtree(): find if any start node can for a subtree which is same with t.

    class Solution {
    public:
        bool isSubtree(TreeNode* s, TreeNode* t) {
            vector<TreeNode*> node_set;
            find_node(s, t, node_set);
            for(auto node : node_set){
                if(is_subtree(node, t)){
                    return true;
                }
            }
            return false;
        }
        
    private:
        void find_node(TreeNode* s, TreeNode* t, vector<TreeNode*>& node_set){
            if(s == NULL){
                return;
            }
            if(s->val == t->val){
                node_set.push_back(s);
            }
            find_node(s->left, t, node_set);
            find_node(s->right, t, node_set);
            return;
        }
    bool is_subtree(TreeNode* s, TreeNode* t){
            if(s == NULL && t == NULL){
                return true;    
            }
            if((s != NULL && t == NULL) || (s == NULL && t != NULL) || (s->val != t->val)){
                return false;
            }
            return is_subtree(s->left, t->left) && is_subtree(s->right, t->right);
        }
    };
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.