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

遞歸過程演示：

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

/**
 * 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é)點
    // 都為空，返回true，說明滿足相同的樹的條件
    if(p == NULL && q == NULL)
    {
        return true;
    }
    // 一個為空一個不為空，返回false
    if(p == NULL || q == NULL)
    {
        return false;
    }
    // 都不為空，但節(jié)點值不相等，返回false
    if(p->val != q->val)
    {
        return false;
    }
    // 2. 經(jīng)過前面的if的判斷，既然運行到這里了，說明當前節(jié)點相等
    // 則繼續(xù)比較左子樹和右子樹的根節(jié)點
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

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

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