题意: 合并两个二叉树, 没有说不可以改变原来的二叉树. 合并的时候把结点求合.
C/C++ 中二叉树的定义
在C或者C++中, 二叉树的定义可以很方便的用结构体来表征. 其中左右子树都是递归定义.
1 2 3 4 5 6 7 | * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ |
* struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
递归, 深度优先
基本上, 算法题中的树类问题都可以用递归来实现, 递归的精髓就是深度优先遍历树.
如果我们不改变输入的两颗二叉树, 我们可以新建一颗二叉树用于合并.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { TreeNode* root; if (t1 == NULL) return t2; if (t2 == NULL) return t1; root = new TreeNode(t1->val + t2->val); root->left = mergeTrees(t1->left, t2->left); root->right = mergeTrees(t1->right, t2->right); return root; } }; |
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { TreeNode* root; if (t1 == NULL) return t2; if (t2 == NULL) return t1; root = new TreeNode(t1->val + t2->val); root->left = mergeTrees(t1->left, t2->left); root->right = mergeTrees(t1->right, t2->right); return root; } };
当然, 代码还可以再简化, 我们可以直接在一棵树上操作.
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; t1->val += t2-gt;val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } }; |
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; t1->val += t2-gt;val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } };
两种递归实现方法的算法复杂度都是 O(m) 其中 m 就是最小结点那个数的结点数. 两种方法的空间复杂度都是 O(m) 因为递归都需要用到堆栈, 并且树有可能是倾斜的, 也就是退化成单向链表. 但平均上, 空间复杂度是 O(logm) – 也就是结点数为 m 的层数.
自己用堆栈实现的DFS深度优先
我们可以用堆栈来自己实现树的深度优先.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; stack< pair<TreeNode*, TreeNode*> > st; st.push(make_pair(t1, t2)); while (st.size() > 0) { auto cur = st.top(); st.pop(); if (cur.first == nullptr || cur.second == nullptr) { continue; } cur.first->val += cur.second->val; // 累加值 if (cur.first->left == nullptr) { // 第一颗树的左树为空, 那么就用第二颗树的左树 cur.first->left = cur.second->left; } else { st.push(make_pair(cur.first->left, cur.second->left)); } if (cur.first->right == nullptr) { // 第一颗树的右树为空, 那么就用第二颗树的右树 cur.first->right = cur.second->right; } else { st.push(make_pair(cur.first->right, cur.second->right)); } } return t1; } }; |
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; stack< pair<TreeNode*, TreeNode*> > st; st.push(make_pair(t1, t2)); while (st.size() > 0) { auto cur = st.top(); st.pop(); if (cur.first == nullptr || cur.second == nullptr) { continue; } cur.first->val += cur.second->val; // 累加值 if (cur.first->left == nullptr) { // 第一颗树的左树为空, 那么就用第二颗树的左树 cur.first->left = cur.second->left; } else { st.push(make_pair(cur.first->left, cur.second->left)); } if (cur.first->right == nullptr) { // 第一颗树的右树为空, 那么就用第二颗树的右树 cur.first->right = cur.second->right; } else { st.push(make_pair(cur.first->right, cur.second->right)); } } return t1; } };
这个和用递归 实现的空间复杂度和算法复杂度都是一样的: O(m)
英文: C++ Coding Exercise – How to Merge Two Binary Trees?
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK