联通做网站,安卓 wordpress 源码分析,巫山网站建设,无水印效果图网站思路详解#xff1a; 总体框架#xff1a;
对root树进行先序遍历#xff0c;如果当前结点#xff08;记为cur#xff09;的值和subRoot的根节点值相等时#xff0c;就开始判断
以cur为根节点的树 和 子树 是否结构一样? 如何判断两棵树是否结构完全相同#xff1f; …
思路详解 总体框架
对root树进行先序遍历如果当前结点记为cur的值和subRoot的根节点值相等时就开始判断
以cur为根节点的树 和 子树 是否结构一样? 如何判断两棵树是否结构完全相同
分析一提到“树”结构很容易想到在先/中/后序遍历上做文章请教了AI后笔者得知如果两棵树先、后序遍历结果完全一样那么便可说明结构完全相同注意先/后序中的一个 中序结果一样 不可说明 这样看来只需要在先/后序遍历中加入结点值的判断就成了 ~ 于是写出两个递归函数
int checkfir(TreeNode* root, TreeNode* subRoot)
{ //先序int re1;if(!root !subRoot) return 1; else if(!root || !subRoot) return 0;if(root-val ! subRoot-val) return 0;re1 checkfir(root-left, subRoot-left);if(re1 0) return 0;re1 checkfir(root-right, subRoot-right);return re1;
}
int checkbac(TreeNode* root, TreeNode* subRoot)
{ //后序//结构于上面类似过程不必再表 ~
} 过程反思
有必要写两个递归函数吗
删了一个递归函数后代码依然AC了...
这是为什么嘞先序和后序只要有一个就好了吗
答案是肯定的因为这函数并不是检验先序的 “最终结果” 是否一致而是检验了“整个遍历过程”是否完全一致
To be specific 函数实现的是两棵树“同步地”走了一遍先序遍历如果每一步都没有出错那就可以说明两颗树结构相同啦
所以最后只保留一个函数即可~ AC代码见下
class Solution {
private:int checkbac(TreeNode* root, TreeNode* subRoot){int re1;if(!root !subRoot) return 1; //trueelse if(!root || !subRoot) return 0;re1 checkbac(root-left, subRoot-left);if(re1 0) return 0;re1 checkbac(root-right, subRoot-right);if(re1 0) return 0;if(root-val ! subRoot-val) return 0;return 1;}
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {int head subRoot-val;if(!root) return false;if(root-val head){if(checkbac(root, subRoot)) return true;}bool re isSubtree(root-left, subRoot);if(re true) return true;re isSubtree(root-right, subRoot);if(re true) return true;return false;}
};
~ 希望对你有启发 ~
