Last Updated on 2023-01-11 by Clay
題目
Given the roots of two binary trees p and q, 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: 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]. -104 <= Node.val <= 104
題目給定兩顆樹狀結構資料，我們要做的是就是比較兩顆樹，如果完全一致則返回 true、不相同則返回 false。
解題思路
遞迴
我們可以直接把題目寫好的 isSameTree() 當作遞迴函式，最基本的案例就是：
- 比較的兩個節點都是空值（nullptr）-> 返回
true - 比較的兩個節點其中一個是空值（nullptr） -> 返回
false - 兩個節點值都不相同 -> 返回
false
之後，就是使用遞迴函式跑左右兩邊的節點。
兩節點走訪 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
// Base case
if (p == nullptr && q == nullptr) {
return true;
}
else if (p == nullptr || q == nullptr) {
return false;
}
else if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};Python 範例程式碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# Base case
if p == None and q == None:
return True
elif p == None or q == None:
return False
elif p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)