100. Same Tree

1. Description

Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

2. Example

Example 1:
Input: [1,2,3], [1,2,3]
Output: true

Example 2:
Input: [1,2], [1,null,2]
Output: false

Example 3:
Input: [1,2,1], [1,1,2]
Output: false

3. Solutions

My Accepted Solution

n is min number of nodes in i_treeP and i_treeQ
Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if (p != nullptr && q != nullptr && p->val == q->val) {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        } else {
            return false;
        }
    }
};