如果「都為空」，則返回 true，說明兩樹相同。
如果「一個(gè)為空一個(gè)不為空」，說明這兩顆樹不相同，則返回 false。
如果「都不為空，但節(jié)點(diǎn)值不相同」，說明這兩顆樹不相同，則返回 false。
經(jīng)過 1 和 2 和 3 的判斷，說明根節(jié)點(diǎn)「都不為空，但節(jié)點(diǎn)值相同」，則當(dāng)前節(jié)點(diǎn)相同。我們繼續(xù)遞歸遍歷，比較它的左子樹和右子樹的根節(jié)點(diǎn)。

遞歸過程演示：

依次比較兩顆二叉樹中「當(dāng)前樹(1、2、3、4、5、6)的根節(jié)點(diǎn)」是否相等，這樣每個(gè)節(jié)點(diǎn)都被比較了一次。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 1. 先比較兩顆樹的根節(jié)點(diǎn)
    // 都為空，返回true，說明滿足相同的樹的條件
    if(p == NULL && q == NULL)
    {
        return true;
    }
    // 一個(gè)為空一個(gè)不為空，返回false
    if(p == NULL || q == NULL)
    {
        return false;
    }
    // 都不為空，但節(jié)點(diǎn)值不相等，返回false
    if(p->val != q->val)
    {
        return false;
    }
    // 2. 經(jīng)過前面的if的判斷，既然運(yùn)行到這里了，說明當(dāng)前節(jié)點(diǎn)相等
    // 則繼續(xù)比較左子樹和右子樹的根節(jié)點(diǎn)
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

時(shí)間復(fù)雜度：假設(shè)兩棵樹都有 n 個(gè)節(jié)點(diǎn)，最多比較 n 次，所以為 O ( N ) O(N) O(N)

空間復(fù)雜度：往下遞歸會(huì)開辟棧幀空間，函數(shù)返回時(shí)會(huì)還給操作系統(tǒng)，所以「空間復(fù)雜度」和「遞歸的最大深度」有關(guān)，最壞情況下，「遞歸的最大深度」就是有 n 的節(jié)點(diǎn)二叉樹的最大深度，所以為 O ( N ) O(N) O(N)