题解 | #牛群的相似结构#

1. 题目考察的知识点

二叉树的基本性质以及基本操作，二叉树的遍历方法

2. 题目解答方法的文字分析

本题的解决方法：运用广度优先搜索来判断两个二叉树是否相同。本质上，两个二叉树是当作完全二叉树来存储的，同时将两个二叉树的每一个同位置的节点一起入队，每次取出两个节点进行位置和值的比较，如有不同，则结构不同.

算法步骤： 1、首先判断两棵二叉树的根节点是否为空，若都是空，则相同。否则为不同。 2、用一个队列存储两个二叉树的节点，初始时将两个二叉树的根节点分别加入同一个队列。每次从一个队列各取出2个节点，进行如下比较操作：首先比较两个节点是否都为空，若任一为空，则结构不相同。然后比较值是否相同，值不同，则结构不同。若以上比较皆相同，则将两个节点的左右节点都入队列。注意，因为每一次比较的是相同位置的两个节点的结构与值，所以入队顺序要一致。 3、当搜索结束时队列为空，则结构相同

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(p==null||q==null){
            return false;
        }
        Queue<TreeNode> listq  = new LinkedList();
        listq.offer(p);
        listq.offer(q);
        while(!listq.isEmpty()){
            TreeNode pchild = listq.poll();
            TreeNode qchild = listq.poll();
            if(pchild==null&&qchild==null){
                continue;
            }
            if(pchild==null||qchild==null||pchild.val!=qchild.val){
                return false;
            }
            listq.offer(pchild.left);
            listq.offer(qchild.left);

            listq.offer(pchild.right);
            listq.offer(qchild.right);

        }
        return true;
   }
}