100. 相同的树

S1: DFS

因为二叉树的子树也是一个二叉树，所以很适合使用递归的方式来解决。

用《产品经理法》来解决递归问题。

定义函数功能，先不用管其具体实现。

我们需要一个函数，给定两个二叉树的根节点，返回这两个二叉树是否相同的判断结果。假设我们已经有这个函数 F，那问题就转化为 F(root1, root2) 了。
确定大问题和小问题的关系。

要解决 F(root1, root2)，明显需要先解决的问题是：
- F(root1.left, root2.left)
- F(root1.right, root2.right)
而它们之间的关系也是显而易见的，两个二叉树要相等的话，当然其根节点和左右子节点都要相等，所以：

F(root1, root2) = root1 === root2 && F(root1.left, root2.left) && F(root1.right, root2.right)
补充递归终止条件
- p, q 都是 null 的时候返回 true
- p, q 只有一个是 null 的时候返回 false
- p, q 值不相同的话返回 false

/**
 * 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;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    if (!p && !q) return true;
    if (!p || !q || p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None: return True
        if p is None or q is None: return False
        if p.val != q.val: return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time: $O(N)$，N 是二叉树的节点总数。
Space: $O(logN)$

S2: BFS

前置：二叉树的层级遍历

对两个二叉树同时进行层级遍历，在遍历过程中逐一比较节点即可。

/**
 * 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;

        queue<TreeNode*> qp; qp.push(p);
        queue<TreeNode*> qq; qq.push(q);

        while (!qp.empty() && !qq.empty()) {
            int sizeP = qp.size();
            int sizeQ = qq.size();
            if (sizeP != sizeQ) return false;
            while (sizeP--) {
                TreeNode* nodeP = qp.front(); qp.pop();
                TreeNode* nodeQ = qq.front(); qq.pop();
                 
                if (nodeP == nullptr && nodeQ == nullptr) continue;
                if (nodeP == nullptr || nodeQ == nullptr) return false;
                if (nodeP->val != nodeQ->val) return false;

                qp.push(nodeP->left); qp.push(nodeP->right);
                qq.push(nodeQ->left); qq.push(nodeQ->right);
            }
        }

        return qp.empty() && qq.empty();

    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
    const queueP = [p];
    const queueQ = [q];

    while (queueP.length && queueQ.length) {
        let lenP = queueP.length;
        let lenQ = queueQ.length;

        // 如果两棵树同一层的节点数都不同，肯定不是同一棵树
        if (lenP !== lenQ) return false;

        while (lenP-- && lenQ--) {
            const nodeP = queueP.shift();
            const nodeQ = queueQ.shift();

            // 两个节点都是 null, 直接继续比较下一个节点
            if (!nodeP && !nodeQ) continue;
            // 遇到不同的节点，说明不是同一棵树，提前返回
            if (!nodeP || !nodeQ || nodeP.val !== nodeQ.val) return false;

            // 将下一层的节点入列，空节点也要入列
            queueP.push(nodeP.left, nodeP.right);
            queueQ.push(nodeQ.left, nodeQ.right);
        }
    }
    return true;
};

Time: $O(N)$，N 是二叉树的节点总数。