常熟祥云平台网站建设,站长推荐自动跳转导航入口,外贸自助建站哪个好,python代码自动生成器牛客热题#xff1a;二叉树与双向链表 #x1f4df;作者主页#xff1a;慢热的陕西人 #x1f334;专栏链接#xff1a;力扣刷题日记 #x1f4e3;欢迎各位大佬#x1f44d;点赞#x1f525;关注#x1f693;收藏#xff0c;#x1f349;留言 文章目录 牛客热题…牛客热题二叉树与双向链表 作者主页慢热的陕西人 专栏链接力扣刷题日记 欢迎各位大佬点赞关注收藏留言 文章目录 牛客热题合并二叉树题目链接方法一递归思路代码复杂度 牛客热题合并二叉树
题目链接
合并二叉树_牛客题霸_牛客网 (nowcoder.com)
方法一递归
思路
将结果集合到t1树上 当t2树为空时直接结束递归当t1和t2都不为空时那么将当前节点的值相加存储在t1树的对应节点 并且去递归他们的子树将t2中存在的节点而t1中不存在的节点都挂到t1树上对应的节点
代码 void _TreeNode(TreeNode* t1, TreeNode* t2) {//两个树为空树的时候递归结束if (t1 nullptr t2 nullptr) return ;//当只有t1树为遍历完得时候也递归结束if (t2 nullptr) return ;//当两棵树都存在该节点时将节点值的加和放到t1对应的节点上if (t1 ! nullptr t2 ! nullptr) {//将当前节点的值相加t1-val t1-val t2-val;//分别去递归左右子树_TreeNode(t1-left, t2-left);_TreeNode(t1-right, t2-right);//t1不存在该节点但是t2存在if (t1-left nullptr t2-left ! nullptr) t1-left t2-left;if (t1-right nullptr t2-right ! nullptr) t1-right t2-right;return ;}}TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {_TreeNode(t1, t2);return t1;}复杂度 时间复杂度O(M N) ,最坏情况下完全遍历两棵树MN分别为两颗树的节点数 空间复杂度O(N) ,最坏情况下,调用的函数栈帧和t2树的节点数相同
