网站怎么上传数据库,湖北做网站平台哪家好,郑州网站建设企业推荐,百度站长平台怎么验证网站❓剑指 Offer 26. 树的子结构
难度#xff1a;中等
输入两棵二叉树 A 和 B#xff0c;判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构#xff0c; 即 A 中有出现和B相同的结构和节点值。
例如: 给定的树 A: 3/ \4 5/ \1 2给定的树 B中等
输入两棵二叉树 A 和 B判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构 即 A 中有出现和B相同的结构和节点值。
例如: 给定的树 A: 3/ \4 5/ \1 2给定的树 B 4 /1返回 true因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1 输入A [1,2,3], B [3,1] 输出false 示例 2 输入A [3,4,5,1,2], B [4,1] 输出true 限制
0 节点个数 10000
思路递归
二叉树 B 为 A 的子结构的情况一共有三种满足其中一种即可
子结构 B 的起点为 A 的根节点即从 A 的根节点开始和 B 比较 调用函数 isSubStree: 不相等则返回 false;相等则再比较 左子树和右子树都是否相等都相等才返回 true 子结构 B 在 A 的左子树中即 B 的起点隐藏在 A 的左子树中此时调用函数 isSubStructure子结构 B 在 A 的右子树中即 B 的起点隐藏在 A 的右子树中此时调用函数 isSubStructure。
代码(C、Java)
C
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:bool isSubStree (TreeNode* root1, TreeNode* root2){if(root2 nullptr) return true;if(root1 nullptr) return false;if(root1-val ! root2-val) return false;return isSubStree(root1-left, root2-left) isSubStree(root1-right, root2-right);}
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(A nullptr || B nullptr) return false;return isSubStree(A, B) || isSubStructure(A-left, B) || isSubStructure(A-right, B);}
};Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {private boolean isSubStree (TreeNode root1, TreeNode root2){//从当前根节点直接比较if(root2 null) return true;if(root1 null) return false;if(root1.val ! root2.val) return false;return isSubStree(root1.left, root2.left) isSubStree(root1.right, root2.right);}public boolean isSubStructure(TreeNode A, TreeNode B) {if(A null || B null) return false;return isSubStree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);}
}运行结果 复杂度分析
时间复杂度 O ( n m ) O(nm) O(nm)其中 n 和 m 分别表示两棵树的节点数我们要对每个 A 树节点进行访问最坏情况下每次都要比较 B 树节点的次数。空间复杂度 O ( n m ) O(n m) O(nm)两个递归栈深度相乘(当树退化成链表时递归栈最大。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
