P82 合并二叉树

描述#

这个题目说的是，给你两棵二叉树，你要把它们合并起来形成一棵新的二叉树。合并规则是对应节点上的数字相加得到新节点的数字，如果有一个节点为空，则直接使用非空节点的数字，如果两个节点都为空，则合并后也为空。

比如说，给你的两棵二叉树是：
1

/ 

3   5
\   

7   9
和
 2
/ \

4   6
/
8
你要返回合并后的二叉树是：
 3
/ \

7   11
/ \    

8   7    9

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 != null && t2 == null) return t1;
    if (t2 != null && t1 == null) return t2;
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
  }

}