题目描述

给你 root1 和 root2 这两棵二叉搜索树。

请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。

样例

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]

输入：root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出：[-10,0,0,1,2,5,7,10]

输入：root1 = [], root2 = [5,1,7,0,2]
输出：[0,1,2,5,7]

输入：root1 = [0,-10,10], root2 = []
输出：[-10,0,10]

输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]

限制

• 每棵树最多有 5000 个节点。
• 每个节点的值在 [-10^5, 10^5] 之间。

算法

(中序遍历) $O(n + m)$

1. 每棵树进行中序遍历，遍历结果存到数组中。
2. 合并两个有序数组。

时间复杂度

• 每个结点遍历常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 递归的系统栈最坏需要 $O(n + m)$ 的空间，中间数组和答案数组也需要 $O(n + m)$ 的空间，故空间复杂度为 $O(n + m)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode *r, vector<int> &s) {
        if (!r)
            return;
        traverse(r -> left, s);
        s.push_back(r -> val);
        traverse(r -> right, s);
    }

    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        vector<int> s1, s2, res;
        traverse(root1, s1);
        traverse(root2, s2);

        int i = 0, j = 0;
        while (i < s1.size() || j < s2.size()) {
            if (j == s2.size())
                res.push_back(s1[i++]);
            else if (i == s1.size())
                res.push_back(s2[j++]);
            else {
                if (s1[i] < s2[j])
                    res.push_back(s1[i++]);
                else
                    res.push_back(s2[j++]);
            }
        }

        return res;
    }
};