做网站站怎么赚钱吗新东方教育培训机构官网

牛客热题：二叉树与双向链表> 📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：合并二叉树

题目链接

合并二叉树_牛客题霸_牛客网 (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树的节点数相同