100 - Same Tree & 572 - Subtree Of Another Tree

100

#easy

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

疊代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> p_queue;
        queue<TreeNode*> q_queue;
        p_queue.push(p);
        q_queue.push(q);
        while ( !p_queue.empty() || !q_queue.empty() ) {
            TreeNode * node_p = p_queue.front();
            p_queue.pop();
            TreeNode * node_q = q_queue.front();
            q_queue.pop();

            if ( node_p == NULL && node_q == NULL ) continue;
            if ( node_p == NULL || node_q == NULL || node_p -> val != node_q -> val ) return false;
            p_queue.push( node_p -> left );
            q_queue.push( node_q -> left );
            p_queue.push( node_p -> right );
            q_queue.push( node_q -> right );
        }

        return true;
    }

Recursive

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        else return compare(left->left, right->left) && compare(left->right, right->right);

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

572

#easy

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

疊代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool compare( TreeNode * cur, TreeNode * subRoot) {
        queue<TreeNode*> que;
        queue<TreeNode*> sub_que;
        que.push( cur );
        sub_que.push( subRoot );
        while ( !que.empty() ) {
            TreeNode * cur_node = que.front();
            que.pop();
            TreeNode * sub_node = sub_que.front();
            sub_que.pop();
            if ( cur_node == NULL && sub_node == NULL ) continue;
            if ( cur_node == NULL || sub_node == NULL || cur_node -> val != sub_node -> val ) return false;
            que.push( cur_node -> left );
            que.push( cur_node -> right );
            sub_que.push( sub_node -> left );
            sub_que.push( sub_node -> right );
        }

        return true;
    }


    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        queue<TreeNode*> que;
        que.push(root);
        while( !que.empty() ) {
            TreeNode * cur = que.front();
            que.pop();
            if ( cur -> val == subRoot -> val && compare( cur, subRoot ) ) return true;
            if ( cur -> left ) que.push( cur -> left );
            if ( cur -> right ) que.push( cur -> right );
        }

        return false;
    }
};

Recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool compare( TreeNode * root, TreeNode * subRoot) {
        if ( root == NULL && subRoot == NULL ) return true;
        if ( root == NULL || subRoot == NULL ) return false;
        if ( root -> val != subRoot -> val ) return false;
        return compare( root -> left, subRoot -> left ) && compare( root -> right, subRoot -> right );
    }


    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if ( subRoot == NULL ) return true;
        if ( root == NULL ) return false;
        bool check = false;
        if(root->val==subRoot->val){
            check = compare(root,subRoot);
        }
        return check || isSubtree( root -> left, subRoot ) || isSubtree( root -> right, subRoot );
    }
};

100

#easy

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

疊代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> p_queue;
        queue<TreeNode*> q_queue;
        p_queue.push(p);
        q_queue.push(q);
        while ( !p_queue.empty() || !q_queue.empty() ) {
            TreeNode * node_p = p_queue.front();
            p_queue.pop();
            TreeNode * node_q = q_queue.front();
            q_queue.pop();

            if ( node_p == NULL && node_q == NULL ) continue;
            if ( node_p == NULL || node_q == NULL || node_p -> val != node_q -> val ) return false;
            p_queue.push( node_p -> left );
            q_queue.push( node_q -> left );
            p_queue.push( node_p -> right );
            q_queue.push( node_q -> right );
        }

        return true;
    }

Recursive

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        else return compare(left->left, right->left) && compare(left->right, right->right);

    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return compare(p, q);
    }
};

572

#easy

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

疊代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool compare( TreeNode * cur, TreeNode * subRoot) {
        queue<TreeNode*> que;
        queue<TreeNode*> sub_que;
        que.push( cur );
        sub_que.push( subRoot );
        while ( !que.empty() ) {
            TreeNode * cur_node = que.front();
            que.pop();
            TreeNode * sub_node = sub_que.front();
            sub_que.pop();
            if ( cur_node == NULL && sub_node == NULL ) continue;
            if ( cur_node == NULL || sub_node == NULL || cur_node -> val != sub_node -> val ) return false;
            que.push( cur_node -> left );
            que.push( cur_node -> right );
            sub_que.push( sub_node -> left );
            sub_que.push( sub_node -> right );
        }

        return true;
    }


    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        queue<TreeNode*> que;
        que.push(root);
        while( !que.empty() ) {
            TreeNode * cur = que.front();
            que.pop();
            if ( cur -> val == subRoot -> val && compare( cur, subRoot ) ) return true;
            if ( cur -> left ) que.push( cur -> left );
            if ( cur -> right ) que.push( cur -> right );
        }

        return false;
    }
};

Recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool compare( TreeNode * root, TreeNode * subRoot) {
        if ( root == NULL && subRoot == NULL ) return true;
        if ( root == NULL || subRoot == NULL ) return false;
        if ( root -> val != subRoot -> val ) return false;
        return compare( root -> left, subRoot -> left ) && compare( root -> right, subRoot -> right );
    }


    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if ( subRoot == NULL ) return true;
        if ( root == NULL ) return false;
        bool check = false;
        if(root->val==subRoot->val){
            check = compare(root,subRoot);
        }
        return check || isSubtree( root -> left, subRoot ) || isSubtree( root -> right, subRoot );
    }
};