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

考察知识点： 数的遍历、深度优先搜索、递归

题目分析：

 题目中要求判断两棵树的结构是否相同，只需要同时遍历两棵树并判断他们的结构是否相同即可。

 写递归的程序时，一般先考虑特殊情况：

1. 当树p和q中一个为空，另一个不为空时，说明结构不同，返回false；
2. 当树p和q都为空时，说明结构暂时相同，返回true；
3. 当结点p的值与结点q的值不同时，说明两棵树不同，返回false；

 然后考虑一般情况：即当树p和q不满足上述特殊情况，我们就要看他们的子树是否满足。即树p的左子树与树q的左子树是否相同，树p的右子树和树q的右子树是否相同，返回这两个问题的与运算结果，即是问题的答案。

所用编程语言： C++

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return bool布尔型
     */
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // write code here
        if ((!p && q) || (!q && p)) return false;
        if (!p && !q) return true;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};