Leetcode 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

Merge two binary trees using depth first search . Traverse two binary trees at the same time from the root node , And merge the corresponding nodes .

The corresponding nodes of two binary trees may exist in the following three cases , Use different consolidation methods for each case .

If the corresponding nodes of two binary trees are empty , The corresponding node of the merged binary tree is also empty ;

If only one of the corresponding nodes of two binary trees is empty , Then the corresponding node of the merged binary tree is the non empty node ;

If the corresponding nodes of two binary trees are not empty , Then the value of the corresponding node of the merged binary tree is the sum of the values of the corresponding nodes of the two binary trees , In this case, you need to explicitly merge the two nodes .

After merging a node , Also merge the left and right subtrees of the node respectively .

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        TreeNode mergeNode = new TreeNode(root1.val + root2.val);
        mergeNode.left = mergeTrees(root1.left,root2.left);
        mergeNode.right =  mergeTrees(root2.right ,root1.right);
        return mergeNode;
    }
}