# 【LeetCode】 100. Same Tree

## Description
> Given two binary trees, 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.

> 給兩棵二元樹，請完成一個function確認兩個樹是不是相同樹。
> 如果兩棵樹是相同的，它們必須擁有同樣結構的節點和同樣的值。

## Example:

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

## Solution

* 在資料結構中我們學過，給予一棵樹的**中序**及**前序**(或**後序**)，我們便可以還原出一棵**唯一樹**。
* 因此，反過來說，只要我們去檢查兩棵樹的遍歷結果是不是相同的，我們就可以得知它們是不是相同的樹。

### Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void getInorder(TreeNode* n,string& str)
    {
        if(n == NULL)
        {
            str+="null";
            return;
        }
        str+=std::to_string(n->val);
        getInorder(n->left,str);
        getInorder(n->right,str);
    }
    void getPreorder(TreeNode* n,string& str)
    {
        if(n == NULL)
        {
            str+="null";
            return;
        }
        getInorder(n->left,str);
        str+=std::to_string(n->val);
        getInorder(n->right,str);
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        string p1,p2,q1,q2;
        getInorder(p,p1);
        getInorder(q,q1);
        getPreorder(p,p2);
        getPreorder(q,q2);
        return p1==q1 && p2==q2;

    }
};

###### tags: `LeetCode` `C++`