剑指offer题目练习及思路分析-JavaScript版(二)
发布日期:2021-06-29 11:52:40
浏览次数:2
分类:技术文章
本文共 1367 字,大约阅读时间需要 4 分钟。
树的子结构
- 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function HasSubtree(pRoot1, pRoot2){ if(!pRoot1 || !pRoot2) { return false; } return isSubTree(pRoot1, pRoot2) || HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);}function isSubTree(root1, root2) { if(!root2) { //Tree2为空,则说明第二棵树遍历完了,即匹配成功 return true; } if(!root1) { //tree1为空有两种情况(1)如果tree1为空&&tree2不为空说明不匹配(2)如果tree1为空,tree2为空,说明匹配。 return false; } if(root1.val == root2.val) { return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right); }else { return false; }}
思路解析:
1、首先设置标志位result = false,因为一旦匹配成功result就设为true, 剩下的代码不会执行,如果匹配不成功,默认返回false 2、递归思想,如果根节点相同则递归调用isSubTree(), 如果根节点不相同,则判断tree1的左子树和tree2是否相同, 再判断右子树和tree2是否相同 3、注意null的条件,HasSubTree中,如果两棵树都不为空才进行判断, isSubTree中,如果Tree2为空,则说明第二棵树遍历完了,即匹配成功, tree1为空有两种情况(1)如果tree1为空&&tree2不为空说明不匹配, (2)如果tree1为空,tree2为空,说明匹配。二叉树的镜像
- 操作给定的二叉树,将其变换为源二叉树的镜像。
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null;} */function Mirror(root){ if(root === null) { return; } var temp = root.left; root.left = root.right; root.right = temp; Mirror(root.left); Mirror(root.right);}
思路解析:
判断树是否为空,然后交换左右子树,最后递归交换左右子树。转载地址:https://blog.csdn.net/zzl819954692/article/details/79783325 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月09日 11时50分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
GD32替换STM32,这些细节一定要知道。
2019-04-29
华为员工离职心声:菊厂15年退休,感恩,让我实现了财务自由!
2019-04-29
春晚上的“拓荒牛”
2019-04-29
嵌入式驱动自学者的亲身感受,有什么建议?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
腾讯机器狗,站起来了!
2019-04-29
我用自己创造的深度学习框架进入腾讯,爽!
2019-04-29
芯片为什么持续缺货?
2019-04-29
又涨了?2021 年 3 月程序员工资统计新出炉
2019-04-29
初入行的C++程序员,如何快速摆脱CRUD阶段?
2019-04-29
研究生跟了一个很棒的导师是种怎样的体验?
2019-04-29
学会扶墙的机器人:没有什么能让我倒下!
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
单片机的几种数字滤波算法
2019-04-29
用单片机控制导弹?
2019-04-29
各种滤波器合集!
2019-04-29
国产CPU深度研究报告(干货,110页)
2019-04-29
在电路中,耦合是什么?有哪些方式?
2019-04-29
变局之际,聊聊物联网的过去、现在和未来
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29