解法一

同时遍历两棵树，判断稍微多做一些，其他和一棵树遍历差不多。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
  12.         if ((t1 == null) && (t2 == null)) {
  13.             return null;
  14.         }
  15.         int sum = 0;
  16.         if (t1 != null) {
  17.             sum += t1.val;
  18.         }
  19.         if (t2 != null) {
  20.             sum += t2.val;
  21.         }
  22.         TreeNode newNode = new TreeNode(sum);
  23.         // Tree 1为空
  24.         if (t1 == null) {
  25.             if (t2.left != null) {
  26.                 newNode.left = mergeTrees(null, t2.left);
  27.             }
  28.             if (t2.right != null) {
  29.                 newNode.right = mergeTrees(null, t2.right);
  30.             }
  31.         } else if (t2 == null) { // Tree 2为空
  32.             if (t1.left != null) {
  33.                 newNode.left = mergeTrees(t1.left, null);
  34.             }
  35.             if (t1.right != null) {
  36.                 newNode.right = mergeTrees(t1.right, null);
  37.             }
  38.         } else { // 均不为空
  39.             newNode.left = mergeTrees(t1.left, t2.left);
  40.             newNode.right = mergeTrees(t1.right, t2.right);
  41.         }
  42.         return newNode;
  43.     }
  44. }