剑指 Offer 26 - 树的子结构
# 📃 题目描述
题目链接:剑指 Offer 26. 树的子结构 (opens new window)
# 🔔 解题思路
乍一看和 572. 另一棵树的子树 (opens new window) 好像是一样的,但其实子树和子结构是不同的!
举个例子:
所谓 root2 是否是 root1 的子结构,其实就是从 root2 开始遍历,对应的从 root1 开始,从否匹配到 root2 上的所有节点。
所以这道题其实是一道 DFS 问题~
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
// 先从根节点判断 B 是不是 A 的子结构,如果不是在分别从左右两个子树判断,
// 只要有一个为true,就说明 B 是 A 的子结构
return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
// dfs 判断 root2 是否是以 root1 为根节点的树的子结构
// 就是从 root2 开始遍历,对应的从 root1 开始,从否匹配到 root2 上的所有节点
private boolean dfs(TreeNode root1, TreeNode root2) {
// 当节点 B 为空:说明树 B 已匹配完成(越过叶子节点),因此返回 true
if (root2 == null) {
return true;
}
// 当节点 A 为空:说明已经越过树 A 叶子节点,即匹配失败,返回 false
// 或者 A.val != B.val,匹配失败,返回 false
if (root1 == null || root1.val != root2.val) {
return false;
}
// 当前节点比较完之后还要继续判断左右子节点
return dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10