【C++算法刷题攻略】二叉树

---

🥰【二叉树】🥰

---

🤩写在前面🤩

• ✨<中序遍历+归并>1305、两棵二叉搜索树中的所有元素✨
• 持续更新中…

🕛 人的才能像挂钟一样，如果停止了摆动，就要落后了~🕛

---

🤩博客内容🤩

✨<中序遍历+归并>1305、两棵二叉搜索树中的所有元素✨

class Solution {
    void inorder(TreeNode *node, vector<int> &res) {
        if (node) {
            inorder(node->left, res);
            res.push_back(node->val);
            inorder(node->right, res);
        }
    }

public:
    vector<int> getAllElements(TreeNode *root1, TreeNode *root2) {
        vector<int> nums1, nums2;
        // 中序遍历获得两棵树的元素升序数组
        inorder(root1, nums1);
        inorder(root2, nums2);
        // 归并排序两个升序数组
        vector<int> merged;
        auto p1 = nums1.begin(), p2 = nums2.begin();
        while (true) {
            if (p1 == nums1.end()) {
                merged.insert(merged.end(), p2, nums2.end());
                break;
            }
            if (p2 == nums2.end()) {
                merged.insert(merged.end(), p1, nums1.end());
                break;
            }
            if (*p1 < *p2) {
                merged.push_back(*p1++);
            } else {
                merged.push_back(*p2++);
            }
        }
        return merged;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> nums1;
    vector<int> nums2;
public:
    void dfs(TreeNode* node, vector<int>& nums) {
        // end
        if(node == nullptr) {
            return;
        }
        // 左中右，中序遍历
        dfs(node->left, nums);
        nums.push_back(node->val);
        dfs(node->right, nums);
        return;
    }
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        dfs(root1, nums1);
        dfs(root2, nums2);
        // 归并， 两数组均升序
        vector<int> ans;
        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()) {
            if(nums1[i] <= nums2[j]) {
                ans.push_back(nums1[i]);
                i++;
            } else {
                ans.push_back(nums2[j]);
                j++;
            }
        }
        while(i < nums1.size()){
            ans.push_back(nums1[i]);
            i++;
        }
        while(j < nums2.size()){
            ans.push_back(nums2[j]);
            j++;
        }        
        return ans;
    }
};

知识点：

• merged.insert(merged.end(), p1, nums1.end()); 数组合并

---

🤩写在后面🤩

🥰加油🥰

🕛 乐观是一首激昂优美的进行曲，时刻鼓舞着你向事业的大路勇猛前进！🕛

---