深度优先搜索

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        /**
         * 如果某棵树为空，则返回另一棵树
         */
        if (root1 == null){
            return root2;
        }

        if (root2 == null){
            return root1;
        }

        /**
         * 新的根节点值为两棵树根节点之和
         */
        TreeNode newRoot = new TreeNode(root1.val + root2.val);

        /**
         * 同时遍历左右子树
         */
        newRoot.left = mergeTrees(root1.left, root2.left);
        newRoot.right = mergeTrees(root1.right, root2.right);
        
        return newRoot;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/merge-two-binary-trees/