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
判断两棵二叉树是否相同。我第一想到的是对两棵树都先序遍历一下，然后看看遍历出来的序列是否一致，如果一致则树是一样的。
class Solution {
public:
void preOrderTraverse(TreeNode* t, vector<int>& res)
{
if (t != NULL) {
res.push_back(t->val);
preOrderTraverse(t->left, res);
preOrderTraverse(t->right, res);
}
}
bool isSameTree(TreeNode* p, TreeNode* q)
{
vector<int> pRes, qRes;
preOrderTraverse(p, pRes);
preOrderTraverse(q, qRes);
if (pRes.size() != qRes.size())
return false;
for (int i = 0; i < pRes.size(); i++) {
if (pRes[i] != qRes[i])
return false;
}
return true;
}
};但是这样做居然是错的！请注意，虽然两棵树的遍历结果是一样的，并不代表这两棵树的结构是一样的。比如[10,5,15]和[10,5,null,null,15]，虽然先序遍历的结果都是10,5,15，但是这两棵树的结构是不一样的。所以不能只看遍历的结果，在遍历的时候就要判断是否相同。如果在同一个位置上，一颗节点为空，另一棵上有值，结构就不一样了。要么两个节点都为空或者有值且相等。
完整代码如下：
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
if (p == NULL && q == NULL)
return true;
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);
}
};本代码提交AC，用时0MS。