泉州手机网站建设公司,wordpress 购物车,wordpress 更换空间,西安app开发文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;572. 另一棵树的子树
2. 题目解析
看到这个题目就感觉不简单#xff0c;因为写了写 dfs 版本的#xff0c;发现好像不太会…
还是简单粗暴一点#xff0c;直接搞一个 前序中序#xff0c;进行判断即可。我… 文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接572. 另一棵树的子树
2. 题目解析
看到这个题目就感觉不简单因为写了写 dfs 版本的发现好像不太会…
还是简单粗暴一点直接搞一个 前序中序进行判断即可。我们知道通过 前序中序是可以构建出一颗唯一的二叉树的当然可以通过 前序中序去判断两颗二叉树是不是一样的。
但这里需要注意的是
我们需要将 NULL 的位置也通过占位标记记录一下不然无法判断子树完全相等只能判断出来存在相同的子结构。例如 但这里需要判断两个 vector a、bb 是否在 a 中出现…这个东西写起来比较耗性能。但在这还是过了。算是一个思路吧。 dfs 每个点都可能是目标子树的根节点同时我们需要判断当根节点确定时该根节点的子树是否等于目标子树。故需要两个递归函数
dfs 函数遍历树上所有节点判断以该节点作为根节点它的子树是否有包含目标子树。 先判断当前根节点是否可以作为目标子树的根节点。再判断根节点的左子树、右子树下的所有节点是否可以作为目标子树的根节点。 check 函数判断节点所处子树是否等于目标子树。 至于其他的写法看官解吧。还是很秀的…
评论区有提到 树上 HASH 的方法字节面试过…让写一下… 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1) 前、中 序判断二叉树。
/*** 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:vectorint a1, a2, b1, b2;void dfs1(TreeNode* root, vectorint v) {if (!root) {v.push_back(1e9); return;}v.push_back(root-val);dfs1(root-left, v);dfs1(root-right, v);}void dfs2(TreeNode* root, vectorint v) {if (!root) {v.push_back(1e9); return;}dfs2(root-left, v);v.push_back(root-val);dfs2(root-right, v);}bool check(vectorint a, vectorint b) {int n a.size(), m b.size();for (int i 0; i n; i ) {bool flag false;for (int k i, j 0; k n j m; j , k ) {if (a[k] ! b[j]) {break;}if (j m - 1) flag true;}if (flag) return true;}return false;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {dfs1(root, a1);dfs2(root, a2);dfs1(subRoot, b1);dfs2(subRoot, b2);return check(a1, b1) check(a2, b2);}
};dfs
/*** 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 check(TreeNode* root, TreeNode* subRoot) {if (!root !subRoot) return true;if (!root subRoot) return false;if (root !subRoot) return false;if (root-val ! subRoot-val) return false;// 同步判断子结构是否一致return check(root-left, subRoot-left) check(root-right, subRoot-right);}// 判断树 root 下是否存在 subRoot 结构的子树bool dfs(TreeNode* root, TreeNode* subRoot) {if (!root) return false;// 先判断root根是否可以作为目标子树的根// root根无法作为目标子树根目标子树根可能存在root的左子树、右子树当中// dfs 判断左子树 是否存在目标子树// dfs 判断右子树 是否存在目标子树return check(root, subRoot) || dfs(root-left, subRoot) || dfs(root-right, subRoot);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {return dfs(root, subRoot);}
};
