博客 | LeetCode 617. Merge Two Binary Trees
博客 | LeetCode 617. Merge Two Binary Trees
本文原载于知乎专栏“LeetCode从易到难”
在日常的业务系统开发中，通常架构设计>数据结构设计>算法设计，架构设计，重在理解业务场景，考虑用户规模和系统适配性的基础上，想清楚每个模块的职责，剩下的就是利用公司的基础组件，比如：分布式Cache和RPC框架，组合起来即可。数据结构设计，重在理清数据流转的基础上，能实现高效存取即可，最常使用的是map，高级点就是bitset，即可满足绝大多数场景需求。而算法设计，业务开发平时真的用不上，虽然在往年的网易云课堂上，参加了王宏志老师的《算法设计与分析》入门篇和进阶篇，并顺利结课，但因常年没有使用和复习，基本也原路退还，但仍怀有“我有基础，有能力解决常见算法问题”的妄念当中。
直到连续倒在3个60%左右接受率的Easy Tree上，才发现问题的严重性。下决心一定要彻底理解Easy Tree的实现逻辑，保证这是最后一篇Easy难度的Tree文章。不保证碰到Medium的时候依旧不会解~嘿嘿~
打开这个问题后：
1，第一个最直观的感受是，可以尝试使用递归求解（树问题的银弹），但因为本身对递归的不熟悉，递归解法都是靠灵感，解题失败；（因为一个点没想到，后面会讲）
2，反而想到二叉树通常可以使用数组表示，只需将2颗树分别以“完美二叉树”的顺序遍历到数组内，nullptr的子节点赋0，接着再按元素相加求和，最后再重新构造一颗二叉树即可；
3，数组的思路，首先遇到的问题就是，如何退出循环。即，如何知道当前节点是树的最后一个有效节点。我的第一思路是，求树高，再按二叉树子节点的公式，以“完美二叉树”遍历后退出即可；
4，所以树高？emmm...，因为常见的树递归解法，通常先使用递归接触到它最左的叶子节点，返回叶子节点的求解值，在函数入口分支返回，再考虑非叶子节点情况下，目标值如何通过叶子节点顺着子节点向上传递，在函数尾部返回目标值即可。树高比较“简单”（不久前才阵亡过），遍历到叶子节点返回0，否则分别递归该节点左，右子树，返回左右子树的树高，则该节点的高度就是左右子树中较大的树高加1，返回即可。所以，任何树递归问题的核心，就是找到目标值传递的方式。《669. Trim a Binary Search Tree》的核心比较容易想：首先是一棵搜索树，其次在边界条件整棵子树都能砍掉；（其实，Merge的核心思路也类似，一时间没联想到）
5，树高完成后，该问题顺利AC，但凭经验肯定是山路十八弯。再回到最初的递归解法，因为有树高的热身，再次回到问题本身的时候，竟然思路顺利很多。但仍然在函数入口跳出循环的步骤上百思不得其解。直到闪电划过脑海，发现如果2棵树的节点中，一棵树的某个节点不存在，那么，合并后的树在这个节点，甚至这个节点的所有子树，都可以复用另一颗树的该节点，因为它理论上也包含了合并后树的所有子树！（类似砍掉整棵树，不受影响）想通了这一点，问题就解决了80%，剩下的20%就是当节点同时存在时，新建节点，然后类似树高的解法一样，新建节点的左右子树分别递归2棵树的左右节点即可。再次AC。
6，递归解法完成后，理论上我也知道任何递归解法都有对应的迭代解法，同时迭代解法一定可以用栈来实现。因为平时后台业务开发中，栈使用极少，更多时候是用队列，一开始也没想清楚栈要如何实现。
7，上网搜索递归转迭代的方法论，思路是：（1）设计数据结构，想清楚栈中元素需要存储的字段，至少包含递归解法中递归函数的参数，它也是核心，其次就是其他标记变量；（2）在主函数入口压栈，模拟第一次进入函数，判断栈空进入循环，模拟不断压栈，直至边界的过程；（3）循环入口至递归调用前的逻辑，模拟函数真正的处理逻辑，栈元素的其他标记变量再此大显身手；（4）递归调用的地方，就是压栈的位置，即函数递归的本质；（5）Over，生搬硬套的递归转迭代方法论。
8，代码如下，老天保佑以后再也不要用Easy Tree的专栏文章！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 栈元素
struct SkItem
{
// 父节点
TreeNode* node = nullptr;
// 的左右节点
bool isLeft = false;
// 当前比较对
pair<TreeNode*, TreeNode*> item;
SkItem(TreeNode* node, bool isLeft, pair<TreeNode*, TreeNode*> item)
: node(node), isLeft(isLeft), item(item) {}
};
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
// 递归法
/*
if (t1 == nullptr) return t2;
if (t2 == nullptr) return t1;
TreeNode* node = new TreeNode(t1->val + t2->val);
node->left = mergeTrees(t1->left, t2->left);
node->right = mergeTrees(t1->right, t2->right);
return node;
*/
// 迭代法
// 入口首先保护
if (t1 == nullptr && t2 == nullptr) return nullptr;
else if (t1 != nullptr && t2 == nullptr) return t1;
else if (t1 == nullptr && t2 != nullptr) return t2;
// 否则，堆栈调用
stack<SkItem> sk;
// 头节点
TreeNode* node = new TreeNode(t1->val + t2->val);
// 压栈左节点
SkItem a(node, true, make_pair(t1->left, t2->left));
sk.push(a);
// 压栈右节点
SkItem b(node, false, make_pair(t1->right, t2->right));
sk.push(b);
while (!sk.empty())
{
// 取出栈顶元素，模仿函数调用
SkItem p = sk.top();
sk.pop();
if (p.item.first == nullptr && p.item.second != nullptr)
{
if (p.isLeft)
{
p.node->left = p.item.second;
}
else
{
p.node->right = p.item.second;
}
}
else if (p.item.first != nullptr && p.item.second == nullptr)
{
if (p.isLeft)
{
p.node->left = p.item.first;
}
else
{
p.node->right = p.item.first;
}
}
else if (p.item.first != nullptr && p.item.second != nullptr)
{
// 子节点
TreeNode* child = new TreeNode(p.item.first->val + p.item.second->val);
// 压栈左节点
SkItem a(child, true, make_pair(p.item.first->left, p.item.second->left));
sk.push(a);
// 压栈右节点
SkItem b(child, false, make_pair(p.item.first->right, p.item.second->right));
sk.push(b);
if (p.isLeft)
{
p.node->left = child;
}
else
{
p.node->right = child;
}
}
}
return node;
}
};