###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 572. Subtree of Another Tree

## [題目連結:] https://leetcode.com/problems/subtree-of-another-tree/

## 題目:
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.



#### [圖片來源:] https://leetcode.com/problems/subtree-of-another-tree/

## 解題想法:

* 可參考: [100. Same Tree](/K2w_YIzyT3S1QZtnpNVYJQ)

* 判斷當前root與subRoot是否為sameTree
* 若是:retrun True
* 否則:遞迴求
* isSubTree(root.left,subRoot) or
* isSubTree(root.right,subRoot)

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def isSubtree(self, root, subRoot):
        """
        :type root: TreeNode
        :type subRoot: TreeNode
        :rtype: bool
        """
        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False
        #root是比較same
        #root.right、root.left是要在遞迴呼叫
        if self.sameTree(root,subRoot):
            return True
        return self.isSubtree(root.left,subRoot) || self.isSubtree(root.right,subRoot)
        
    def sameTree(self,p,q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val==q.val:
            return self.sameTree(p.left,q.left) && self.sameTree(p.right,q.right)
        return False

if __name__ == '__main__':
    root = TreeNode(3)
    root.insertLeft(4)
    root.insertRight(5)
    root.left.insertLeft(1)
    root.left.insertRight(2)
    root.left.right.insertLeft(0)
    root.printTree()
    
    subRoot = TreeNode(4)
    subRoot.insertLeft(1)
    subRoot.insertRight(2)
    subRoot.printTree()
    
    result = Solution()
    ans = result.isSubtree(root,subRoot)
    print(ans)

## C++:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

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) {}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr){
        InsertLeft(tmp->left,data);
    }
    else{
        TreeNode *new_node = new TreeNode(data);
        tmp->left=new_node;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->right!=nullptr){
        InsertRight(tmp->right,data);
    }
    else{
        TreeNode *new_node = new TreeNode(data);
        tmp->right=new_node;
    }
}

void printTree(TreeNode* root){
    TreeNode *tmp=root;
    queue<TreeNode*> que;
    vector<int> res;
    que.push(tmp);
    while (!que.empty()){
        TreeNode *cur = que.front(); que.pop();
        res.push_back(cur->val);
        if (cur->left)
            que.push(cur->left);
        if (cur->right)
            que.push(cur->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;

}

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root && !subRoot)
            return true;
        if (!root || !subRoot)
            return false;
        if (sameTree(root,subRoot))
            return true;
        return isSubtree(root->left,subRoot) or isSubtree(root->right,subRoot);
    }
    bool sameTree(TreeNode* p, TreeNode *q){
        if (!p && !q)
            return true;
        if (!p || !q)
            return false;
        if (p->val==q->val)
            return sameTree(p->left,q->left) and sameTree(p->right,q->right);
        return false;
    }
};

int main(){
    TreeNode *root=new TreeNode(3);
    InsertLeft(root,4);
    InsertRight(root,5);
    InsertLeft(root->left,1);
    InsertRight(root->left,2);

    TreeNode *subRoot= new TreeNode(4);
    InsertLeft(subRoot,1);
    InsertRight(subRoot,2);

    cout<<"Root   : ";
    printTree(root);
    cout<<"SubRoot: ";
    printTree(subRoot);

    Solution res;
    bool ans = res.isSubtree(root,subRoot);
    cout<<ans<<endl;
    return 0;
}