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

# 100. Same Tree

## [題目來源:] https://leetcode.com/problems/same-tree/

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

## 解題思路:
遞迴比較root.val、左子、右子

## 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 isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val==q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

p=TreeNode(1)
p.insertLeft(2)
p.insertRight(3)

q=TreeNode(1)
q.insertLeft(2)
q.insertRight(3)

result=Solution()
ans=result.isSameTree(p,q)
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;
    while (tmp->left != nullptr){
        tmp=tmp->left;
    }
    TreeNode *new_left=new TreeNode(data);
    tmp->left=new_left;
}

void insertRight(TreeNode *root,int data){
    TreeNode *tmp=root;
    while (tmp->right != nullptr){
        tmp=tmp->right;
    }
    TreeNode *new_right= new TreeNode(data);
    tmp->right= new_right;
}

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 isSameTree(TreeNode *p, TreeNode *q){
        if (p==nullptr && q==nullptr)
            return true;
        if (!p || !q)
            return false;
        if (p->val == q->val){
            return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
        }
        return false;
    }
};


int main(){
    TreeNode *p = new TreeNode(1);
    insertLeft(p,2);
    insertRight(p,3);
    cout<<"Tree P:";
    printTree(p);

    TreeNode *q = new TreeNode(1);
    insertLeft(q,2);
    insertRight(q,3);
    cout<<"Tree Q:";
    printTree(q);

    Solution res;
    bool ans=res.isSameTree(p,q);
    cout<<ans<<endl;
    cout<<"Time Space:O(N)";
    return 0;
}