DFS 归并排序

方法一DFS + 归并排序

首先中序遍历两颗数，由于二叉树的性质，中序遍历得到的两个数组是有序的，然后对两个数组进行归并排序得出答案

参考代码

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
  9.         def dfs(root,res):
  10.             if root:
  11.                 dfs(root.left,res)
  12.                 res.append(root.val)
  13.                 dfs(root.right,res)
  15.         nums1,nums2 = [],[]
  16.         dfs(root1,nums1)
  17.         dfs(root2,nums2)
  19.         merged = []
  20.         p1, n1 = 0, len(nums1)
  21.         p2, n2 = 0, len(nums2)
  23.         while True:
  24.             if p1 == n1:
  25.                 merged.extend(nums2[p2:])
  26.                 break
  27.             elif p2 == n2:
  28.                 merged.extend(nums1[p1:])
  29.                 break
  30.             elif nums1[p1] > nums2[p2]:
  31.                 merged.append(nums2[p2])
  32.                 p2 += 1
  33.             else:
  34.                 merged.append(nums1[p1])
  35.                 p1 += 1
  37.         return merged

复杂度分析

时间复杂度：O(n+m)，其中 n 和 m 分别为两棵二叉搜索树的节点个数。
空间复杂度：O(n+m)。存储数组以及递归时的栈空间均为 O(n+m)。