合并二叉树

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

经验1：

程序写在递归函数前面代表压栈的时候实现，也就是说浏览到这个结点的时候实现

程序写在递归函数后面代表弹栈的时候实现，也就是下一次递归结束后在本次递归函数中实现

那么到底是压栈的时候实现还是弹栈的时候实现呢，这要看对根节点的操作会不会对子节点的操作造成影响，如果会造成影响那么一定要在弹栈的时候实现，这也是下面的代码出错的原因。

下面代码为什么出错呢：原因是我将“如果tree1这个位置上的结点如果为空，tree2这个位置上的结点不为空，那么将tree2这个位置的结点填到tree1这个位置上去”这段程序写到递归之前了，那么这就导致对根节点的操作对子节点的操作造成了影响：

注意对返回值的操作也属于写在递归后

也就是只有下一层的递归执行完了才会由返回值返回给这一层

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     void process(TreeNode* root1, TreeNode* root2){
15         if(root1->left==nullptr&&root2->left==nullptr&&root1->right==nullptr&&root2->right==nullptr) return;
16         if(root1->left!=nullptr&&root2->left!=nullptr) root1->left->val+=root2->left->val;
17         if(root1->left!=nullptr&&root2->left==nullptr) root1->left->val=root1->left->val;
18         if(root1->left==nullptr&&root2->left!=nullptr) root1->left=root2->left;
19         if(root1->right!=nullptr&&root2->right!=nullptr) root1->right->val+=root2->right->val;
20         if(root1->right!=nullptr&&root2->right==nullptr) root1->right->val=root1->right->val;
21         if(root1->right==nullptr&&root2->right!=nullptr) root1->right=root2->right;
22 
23         if(root1->left&&root2->left) process(root1->left,root2->left);
24         if(root1->right&&root2->right) process(root1->right,root2->right);
25     }
26     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
27        if(root1==nullptr&&root2==nullptr) return root1;
28        else if(root1!=nullptr&&root2==nullptr) return root1;
29        else if(root1==nullptr&&root2!=nullptr) return root2;
30        else root1->val+=root2->val;
31        process(root1,root2);
32        return root1;
33     }
34 };

经验2：

如何实现子结点和父节点一起操作呢，首先在子节点的递归中是行不通的，那么只能将子节点返回到父节点的递归中这个时候可以在父节点的递归中实现对子节点和父节点的同时操作：