100. Same Tree
- Hardness: \(\color{green}\textsf{Easy}\)
- Ralated Topics:
Tree、Depth-First Search、Breadth-First Search、Binary Tree
一、題目
Given the roots of two binary tree p and q, write a function to check if they are the same or not.
Two binary tree are considered the same if they are structurally iedntical, and the nodes have the same value.
Example 1:
- Input: p = [1,2,3], q = [1,2,3]
- Output: true
Example 2:
- Input: p = [1,2], q = [1,null,2]
- Output: false
Example 3:
- Input: p = [1,2,1], q = [1,1,2]
- Output: false
Constraints:
- The number of nodes in both trees is in the range
[0, 100]. -10^4 <= Node.val <= 10^4
二、分析
- 典型樹的遍歷問題，兩棵樹一起遍歷，注意要處理當
node == null的情形便可。 - 兩棵樹相同的條件為：
root的值相同，且左右兩個leaf也相同。
三、解題
1. Recursion
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)
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);
}