DFS

方法一DFS模拟

参考代码

  1. class Solution:
  2.     def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
  3.         if not root1:
  4.             return root2
  5.         if not root2:
  6.             return root1
  7.         merge = TreeNode(root1.val + root2.val,self.mergeTrees(root1.left,root2.left),self.mergeTrees(root1.right,root2.right))
  8.         return merge

复杂度分析

时间复杂度O(min(m,n)) m,n为两个树的节点个数，最坏情况是单支树
空间复杂度 O(min(m,n))主要是递归调用栈空间