LeetCode 0100 - Same Tree
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
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 .
# 题意
给定两棵二叉树,判断二者是否完全等价,即树结构和对应位置节点值都完全相同。
# 题解
水题,直接 DFS 即可。
# AC代码
/**
* 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) {
// 特判
if (p == nullptr || q == nullptr) {
return (p == nullptr && q == nullptr);
}
// DFS
return dfs(p, q);
}
// 深度优先搜索
bool dfs(TreeNode * p, TreeNode * q) {
// 检查
if (p->val != q->val ||
(p->left == nullptr) != (q->left == nullptr) ||
(p->right == nullptr) != (q->right == nullptr)) {
return false;
}
// 递归
bool flag = true;
if (p->left != nullptr) flag &= dfs(p->left, q->left);
if (p->right != nullptr) flag &= dfs(p->right, q->right);
return flag;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01