---
tags: LeetCode
---

# 100. Same Tree
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.

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

輸入範本如下

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        
    }
}

### 直覺想法
使用遞迴 , 先檢查目前走訪的這個位置 , 兩顆 tree 的值是否相同 , 若結構以及值都相同 , 則繼續走訪下一個位置.
DFS 走訪順序為 中左右.

92 ms	24.4 MB
You are here!
Your runtime beats 74.14 % of csharp submissions.
public bool IsSameTree(TreeNode p, TreeNode q)
{
     if (p != null && q != null && p.val == q.val)
     {
          return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
     }
     return p == q; // 只有 p == q == null 才會為 true
}

試圖使用兩個 Queue 採用 BFS 的方式去比較兩棵樹.

88 ms	24.2 MB
You are here!
Your runtime beats 92.63 % of csharp submissions.
public bool IsSameTree(TreeNode p, TreeNode q)
{
     Queue<TreeNode> pQueue = new Queue<TreeNode>();
     Queue<TreeNode> qQueue = new Queue<TreeNode>();
     pQueue.Enqueue(p);
     qQueue.Enqueue(q);
     while (pQueue.Count > 0 && qQueue.Count > 0)
     {
          var currP = pQueue.Dequeue();
          var currQ = qQueue.Dequeue();
          if (currP != null && currQ != null && currP.val == currQ.val)
          {
               pQueue.Enqueue(currP.left);
               qQueue.Enqueue(currQ.left);
               pQueue.Enqueue(currP.right);
               qQueue.Enqueue(currQ.right);
          }
          else if (currP == currQ)
          {
          }
          else
          {    // 左右兩兒子的結構不同或是 currP.val != currQ.val
               return false;
          }
     }
     return true; // 所有點都比較過 , 且值都相等
}

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: