617. Merge binary tree (easy)

617. Merge binary tree

Given two binary trees , Imagine when you overlay one of them on the other , Some nodes of two binary trees will overlap .

You need to merge them into a new binary tree . The rule for merging is if two nodes overlap , Then add their values as the new values after node merging , Otherwise, no NULL The node of will be the node of the new binary tree directly .

Example 1:

 Input : 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
 Output : 
 Merged tree :
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
 Be careful :  The merge must start at the root of both trees .

Ideas

Two ways

• The first one is , Directly change the value of a node in a node , Then return to this node ;
• The second kind , Create a new tree from two trees , And return the head node of the new tree
  Here we use the first method ,dfs Search two trees at the same time , The return condition is that if a node is empty, it will directly return to another node .

Source code

class Solution {
    
public:
    TreeNode* dfs(TreeNode* root1, TreeNode* root2) {
    
        if (root1 == nullptr || root2 == nullptr) {
    //  If a node is empty , The node that is not empty is returned   Or it's all empty , Return empty node 
            return root1 == nullptr ? root2 : root1;
        }
        //  When all nodes exist 
        root1->val += root2->val;//  The node value becomes the sum of two nodes 
        root1->left = dfs(root1->left,root2->left);//  Left recursion 
        root1->right = dfs(root1->right,root2->right);//  Right recursion 
        return root1;
    }
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    
        if (root1 == nullptr || root2 == nullptr) {
    //  If one of the root nodes is empty ,  The node that is not empty is returned   Or it's all empty , Return empty node 
            return root1 == nullptr ? root2 : root1;
        }
        dfs(root1,root2);
        return root1;
    }
};