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

殺【二叉树】殺

朗写在前面朗

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

朗博客内容朗

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

public:
    vector getAllElements(TreeNode *root1, TreeNode *root2) {
        vector nums1, nums2;
        // 中序遍历获得两棵树的元素升序数组
        inorder(root1, nums1);
        inorder(root2, nums2);
        // 归并排序两个升序数组
        vector 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;
    }
};

class Solution {
    vector nums1;
    vector nums2;
public:
    void dfs(TreeNode* node, vector& nums) {
        // end
        if(node == nullptr) {
            return;
        }
        // 左中右，中序遍历
        dfs(node->left, nums);
        nums.push_back(node->val);
        dfs(node->right, nums);
        return;
    }
    vector getAllElements(TreeNode* root1, TreeNode* root2) {
        dfs(root1, nums1);
        dfs(root2, nums2);
        // 归并， 两数组均升序
        vector 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()); 数组合并

朗写在后面朗

殺加油殺