leetcode 1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]

Constraints:

Each tree has at most 5000 nodes.
Each node's value is between [-10^5, 10^5].

题目大意：给定两颗二叉搜索树，返回一个升序的列表，列表中的元素是两棵树的节点值。

思路：二叉搜索树的中序遍历是非减的序列，因此可以先对两个二叉搜索树进行中序遍历得到两个非减序列，再合并两个序列。

 1 class Solution {
 2     //中序遍历并保存
 3     void traverse(TreeNode *root, vector<int> &v){
 4         if (root == nullptr)
 5             return;
 6         traverse(root->left, v);
 7         v.push_back(root->val);
 8         traverse(root->right, v);
 9     }
10     //合并两个vector
11     vector<int> merge(vector<int> v1, vector<int> v2) {
12         vector<int> v(v1.size()+v2.size());
13         int i = 0, j = 0, index = 0;
14         while (i < v1.size() || j < v2.size()) {
15             if ((j == v2.size()) || (i < v1.size() && v1[i] <= v2[j])) 
16                 v[index++] = v1[i++];
17             else
18                 v[index++] = v2[j++];
19         }
20         return v;
21     }
22 public:
23     vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
24         // ios_base::sync_with_stdio(false);
25         ios::sync_with_stdio(false);
26         cin.tie(NULL);
27         
28         vector<int> v1, v2;
29         traverse(root1, v1);
30         traverse(root2, v2);
31         
32         return merge(v1, v2);
33     }
34 };

时间复杂度：O(n),

空间复杂度：O(n)

python3:

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def dfs(self, root, arr):
10         if not root:
11             return 
12         self.dfs(root.left, arr)
13         arr.append(root.val)
14         self.dfs(root.right, arr)
15             
16     def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
17         # def dfs(root, ans):
18         #     if not root:
19         #         return
20         #     dfs(root.left, ans)
21         #     ans.append(root.val)
22         #     dfs(root.right, ans)
23         
24         list1, list2 = [], []
25         self.dfs(root1, list1)
26         self.dfs(root2, list2)
27         list1.extend(list2)
28         list1.sort()
29         return list1
30         # i, j = 0, 0
31         # res = []
32         # while i < len(list1) or j < len(list2):
33         #     if (j >= len(list2) or (i < len(list1) and (list1[i] <= list2[j]))):
34         #         res.append(list1[i])
35         #         i += 1
36         #     else:
37         #         res.append(list2[j])
38         #         j += 1
39         # return res