网站短信验证怎么做,专门做情侣装的网站,阿里巴巴网站建设哪家好,衡阳网站建设设计树的子结构 输入两棵二叉树 A#xff0c;B#xff0c;判断 B 是不是 A 的子结构。
我们规定空树不是任何树的子结构。
数据范围
每棵树的节点数量 [ 0 , 1000 ] [0,1000] [0,1000]。
样例
树 A#xff1a; 8/ \8 7/ \9 2/ \4 7树 B#xff1a; 8/ \9 2返回 t…树的子结构 输入两棵二叉树 AB判断 B 是不是 A 的子结构。
我们规定空树不是任何树的子结构。
数据范围
每棵树的节点数量 [ 0 , 1000 ] [0,1000] [0,1000]。
样例
树 A 8/ \8 7/ \9 2/ \4 7树 B 8/ \9 2返回 true因为 B 是 A 的子结构。 算法思路
第一部分遍历树A
递归遍历树A中的所有非空节点R对每个非空节点R进行第二部分的匹配判断
第二部分子树匹配判断
同时从根节点开始遍历两棵子树
终止条件 如果树B中的节点为空 → 匹配成功返回true如果树A中的节点为空但树B不为空 → 匹配失败返回false如果两节点都不为空但值不同 → 匹配失败返回false 递归判断 当前节点匹配成功后递归判断左右子树
时间复杂度分析
最坏情况需要遍历树A中的每个节点n个对每个节点都要完整遍历树Bm个时间复杂度O(n×m) n树A的节点数m树B的节点数
/*** 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 {
public:bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if(!pRoot1 || !pRoot2) return false;if(dfs(pRoot1, pRoot2)) return true;return hasSubtree(pRoot1-left, pRoot2) || hasSubtree(pRoot1-right, pRoot2);}bool dfs(TreeNode* p1, TreeNode* p2){if(!p2) return true;if(!p1 || p1-val ! p2-val) return false;return dfs(p1-left, p2-left) dfs(p1-right, p2-right);}
};
