题目地址：https://leetcode-cn.com/problems/merge-two-binary-trees/
    难度：简单
    思路：大部分涉及到二叉树的算法，都会涉及递归。
    image.png
    对于一棵二叉树，比较推荐的思考习惯是，只思考一个节点上需要进行哪些操作，否则就绕进去了。
    因此，不论对于根节点还是叶子节点，合并两颗二叉树在这个节点上的操作内容都是类似的：

    • 判断两颗二叉树在该节点上是否需要进行处理（最直观的就是根节点）：
      1. 两棵树在当前节点都有值的情况，值相加（合并），否则就把有值的节点“拷”过去即可
      2. 观察当前节点的左、右子树，对左右子树进行等价的递归操作。

    这里因为需要返回合并了两颗二叉树之后的新二叉树，因此，需要从创建根节点开始。

    1. public class Solution {
    2.     public TreeNode mergeTwoBinaryTrees(TreeNode root1, TreeNode root2) {
    3.         // 边界情况
    4.         if (root1 == null) {
    5.             return root2;
    6.         }
    7.         if (root2 == null) {
    8.             return root1;
    9.         }
    10.         // 创建一个新的二叉树根节点
    11.         TreeNode root = new TreeNode(root1.val + root2.val);
    13.         // 对合并后的新二叉树的左子树进行递归操作
    14.         root.left = mergeTwoBinaryTrees(root1.left, root2.left);
    15.         // 对合并后的新二叉树的右子树进行递归操作
    16.         root.right = mergeTwoBinaryTrees(root1.right, root2.right);
    18.         return root;
    19.     }
    20. }

    空间复杂度：因为是两棵树合并，因此，空间复杂度为O(min(M, N))，M和N分别是两颗树的节点个数。
    时间复杂度：由于是递归调用，则时间复杂度为O(h)，h为树的高度，最坏情况下，一棵二叉树退化成了链表，则时间复杂度就变为二叉树的节点个数了。