Merge Two Binary Tree- LeetCode I solved this problem on LeetCode


  Given two binary trees and imagine that when you put one of them to
  cover the other, some nodes of the two trees are overlapped while the
  others are not.
  
  You need to merge them into a new binary tree. The merge rule is that
  if two nodes overlap, then sum node values up as the new value of the
  merged node. Otherwise, the NOT null node will be used as the node of
  new tree.

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

  
  Note: The merging process must start from the root nodes of both trees.


The code that I had written is.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public enum Direction
    {
        Left, Right, None
    }
    public TreeNode doMerge(TreeNode t1, TreeNode t2, Direction direction, TreeNode t3)
        {
            if(t1 == null &amp;&amp; t2 == null)
            {
                return t3;
            }
            if(t1 == null || t2 == null)
            {
                TreeNode notNullTree = t1 == null ? t2 : t1;
                switch(direction)
                {
                    case Direction.None:
                        return notNullTree;
                    case Direction.Left:
                        t3.left = notNullTree;
                        break;
                    case Direction.Right:
                        t3.right = notNullTree;
                        break;
                }
                return t3;
            }
            var newNode = new TreeNode(t1.val + t2.val);
            switch (direction)
            {

                case Direction.None:
                    t3 = newNode;
                    break;
                case Direction.Left:
                    t3.left = newNode;
                    t3 = t3.left;
                    break;
                case Direction.Right:
                    t3.right = newNode;
                    t3 = t3.right;
                    break;
            }
            doMerge(t1.left, t2.left, Direction.Left, t3);
            doMerge(t1.right, t2.right, Direction.Right, t3);
            return t3;
        }
        public TreeNode MergeTrees(TreeNode t1, TreeNode t2)
        {
            return doMerge(t1, t2, Direction.None, null);
        }
}


The code has a lot of conditionals which could be refactored. Any suggestion on making the code a bit cleaner and concise would be helpful.
This is a very interesting problem! 

Firstly, you have correctly identified the 3 possible states:


both tree1 and tree2 are null
tree1 or tree2 is null
both tree1 and tree2 are not null


That being said, I would recommend a couple of things:


Break up the problem into 4 possible states (i.e., don't handle the case when tree1 or tree2 is null in one conditional statement.
if passing in the merged tree tree3 to doMerge in order to modify it in the method, you should utilize C#'s out parameter.
Why do you need the Direction enum? It seems to make the code harder to understand.


Here is my implementation of doMerge:

public TreeNode MergeTrees(TreeNode t1, TreeNode t2) 
{
    if (t1 == null &amp;&amp; t2 == null) return null;
    if (t1 != null &amp;&amp; t2 == null) return t1;
    if (t1 == null &amp;&amp; t2 != null) return t2;
    TreeNode merged = new TreeNode(t1.val + t2.val);
    merged.left = MergeTrees(t1.left, t2.left);
    merged.right = MergeTrees(t1.right, t2.right);
    return merged;
}