题解 | 两棵二叉搜索树中所有元素

题干分析

题设给定两颗二叉搜索树，要求我们返回包含这两颗树所有节点值的升序数组。

算法思路

利用二叉搜索树中序遍历结果即为所有节点值组成的升序数组的性质，对两颗树进行中序遍历，得到各自的遍历数组，后按序合并即可。

实现代码

class Solution {
    vector<int> inOrder;

    void clear() {
        inOrder.clear();
    }
    
    void dfs(TreeNode *node) {
        if (node) {
            dfs(node->left);
            inOrder.push_back(node->val);
            dfs(node->right);
        }
    }
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        clear();
        dfs(root1);
        auto tmp1 = inOrder;
        int n1 = static_cast<int>(tmp1.size());
        
        clear();
        dfs(root2);
        auto tmp2 = inOrder;
        int n2 = static_cast<int>(tmp2.size());
        
        int i = 0, j = 0;
        vector<int> ans;
        while (i < n1 && j < n2) {
            if (tmp1[i] < tmp2[j]) {
                ans.push_back(tmp1[i]);
                ++i;
            } else {
                ans.push_back(tmp2[j]);
                ++j;
            }
        }
        while (i < n1) {
            ans.push_back(tmp1[i]);
            ++i;
        }
        while (j < n2) {
            ans.push_back(tmp2[j]);
            ++j;
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：每个节点访问常数次，时间复杂度为
• 空间复杂度：暂存数组，递归最坏，总计仍为