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

Solution

1. BSF：用兩個Queue分別記錄Tree1, Tree2的節(jié)點
2. 每層遍歷時埠忘，
   • 如果兩棵樹的當(dāng)前層的節(jié)點數(shù)不等時 （Queue.size () 不等），說明節(jié)點數(shù)不一致，不是Same Tree,直接返回false向叉。
   • 如果兩棵樹當(dāng)前的節(jié)點都為null，直接跳過判斷下一個節(jié)點
   • 如果兩棵樹伪窖，當(dāng)前節(jié)點有任一一個為null，或都不為null但value不等居兆。也不是Same Tree,直接返回false覆山。

Note: 注意Example2中兩棵樹是不等的，所以如果左右子樹為空時泥栖，也需要在BSF中推入Queue簇宽，否則無法區(qū)別這種情況勋篓。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        
        if (p == null || q == null) {
            return false;
        }
        
        Queue<TreeNode> tracker1 = new LinkedList<> ();
        Queue<TreeNode> tracker2 = new LinkedList<> ();
        
        tracker1.offer (p);
        tracker2.offer (q);
        
        while (!tracker1.isEmpty () && !tracker2.isEmpty()) {
            int pSize = tracker1.size ();
            int qSize = tracker2.size ();
            
            if (pSize != qSize) {
                return false;
            }
            
            for (int i = 0; i < pSize; i++) {
                TreeNode pNode = tracker1.poll ();
                TreeNode qNode = tracker2.poll ();
                
                if (pNode == null && qNode == null) {
                    continue;
                }
                
                if ((pNode == null || qNode == null) || (pNode != null && qNode != null && pNode.val != qNode.val)) {
                    return false;
                }
                
                tracker1.offer (pNode.left);
                tracker1.offer (pNode.right);
                tracker2.offer (qNode.left);
                tracker2.offer (qNode.right);
            }
        }
        
        return true;
    }
}