LeetCode 100. Same Tree

题目

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.

Example 1:

Input:
1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true

Example 2:

Input:
1 1
/   \
2   2
[1,2], [1,null,2]
Output: false

Example 3:

Input:
1   1
/ \  / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false

解析

树相关的知识在工作中用的比较少，因此有些生疏。判断两根树相同不相同，类似于遍历，如前序遍历，根-->左子树-->右子树。两颗树是否相同，根-->左子树-->右子树。但是NULL情况需要注意一下：
（1）当前p和q均为NULL时，返回true；
（2）当前p和q只有一个为NULL，返回false；
还需要判断val的值是否相等，然后开始遍历左子树和右子树。
此题和LeetCode 101. Symmetric Tree一样，不过对称树要注意判断的是(left->left, right->right) && (left->right, right->left)。

代码（C语言）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL)
        return true;
    else if (p == NULL || q == NULL)
        return false;
    
    if (p->val != q->val)
        return false;
    
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

最后，判断左子树和右子树是否相等，返回结果。