做公司网站需要什么资料,网络营销论文选题,设计网站开发费用计入什么科目,北京移动端网站优化题目#xff1a;
检查子树。你有两棵非常大的二叉树#xff1a;T1#xff0c;有几万个节点#xff1b;T2#xff0c;有几万个节点。设计一个算法#xff0c;判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n#xff0c;其子树与 T2 一模一样#xff0c;则 T2 为…题目
检查子树。你有两棵非常大的二叉树T1有几万个节点T2有几万个节点。设计一个算法判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n其子树与 T2 一模一样则 T2 为 T1 的子树也就是说从节点 n 处把树砍断得到的树与 T2 完全相同。
注意这道题与找不同的地方在于“从节点 n 处把树砍断得到的树与 T2 完全相同”所以必须要找到叶子节点这期间的所有节点都相同才是子树否则不是子树
示例 输入t1 [1, 2, 3], t2 [2] 输出true 输入t1 [1, 2, 345], t2 [2] 输出false 解题思路
1.先递归地找到T1树中与T2的根节点相同的节点
2.再递归地找剩下的节点是否每一个都相等 源代码如下
class Solution {
public:bool dfs(TreeNode* t1,TreeNode* t2){if(t1NULLt2NULL) return true;//同时为空返回trueif(t1NULL||t2NULL) return false;//只有一个为空则一定不相等返回false//节点值相等 继续递归if(t1-valt2-val){return dfs(t1-left,t2-left)dfs(t1-right,t2-right);}//一旦出现不相等的情况直接返回falseelse return false;}bool checkSubTree(TreeNode* t1, TreeNode* t2) {if(t1NULLt2NULL) return true;//两颗都是空树则返回trueif(t1NULL||t2NULL) return false;//只有一颗树为空那么一定不存在子树返回false//如果T1节点的值与T2的节点值相同则开始递归的找其他节点是否相等if(t1-valt2-val){if(dfs(t1,t2)){return true;}}//在T1中找到与T2根节点值相同的节点return checkSubTree(t1-left,t2)||checkSubTree(t1-right,t2);}
};
