相同的树-100

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

Input: p = [1,2,3], q = [1,2,3]
Output: true

示例 2：

Input: p = [1,2], q = [1,null,2]
Output: false

示例 3：

Input: p = [1,2,1], q = [1,1,2]
Output: false

提示：

• -10≤ Node.val ≤ 10
• 两棵树上的节点数目都在范围 [0, 100] 内

思路

先判断最极端的条件：

• 两个节点都是nullptr；
• 其中一个节点是nullptr；
• 到了叶子节点，但是两个节点的值不相等；

判断完后直接递归搜索就行。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if( p == nullptr && q == nullptr )      return true;
        if( p == nullptr || q == nullptr )      return false;
        if( p->val != q->val )                  return false;
        bool result = (
            isSameTree(p->left, q->left) &&
            isSameTree(p->right, q->right) 
        );
        return result;
    }
};