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
給定兩個二叉樹,編寫一個函數來檢查它們是否相同。
如果兩個二叉樹在結構上相同并且節點具有相同的值,則認為它們是相同的。
思路
1.如果p和q其中有一個是空樹,那麼不可能相等,傳回false
2.每次遞歸檢視值是否相等,如果相等,遞歸判斷左右子樹是否相等
3.其他情況都return false
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(!p && !q){
return true;
}else if(p && q && (p->val == q->val)){
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}else{
return false;
}
}