刷题《剑指Offer》day02

题目来源：力扣《剑指Offer》第二版
完成时间：2022/07/23

07. 重建二叉树

我的题解

/** * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    
        if(preorder.size() == 0){
    
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[0]);
        int index = 0;
        for(int i = 0;i < inorder.size();i++) {
    
            if(inorder[i] == root->val){
    
                index = i;
                break;
            }
        }
        preorder.erase(preorder.begin());
        vector<int> leftPreorder(preorder.begin(),preorder.begin() + index);
        vector<int> rightPreorder(preorder.begin() + index,preorder.end());
        vector<int> leftInorder(inorder.begin(),inorder.begin() + index);
        vector<int> rightInorder(inorder.begin() + index + 1,inorder.end());
        root->left = buildTree(leftPreorder,leftInorder);
        root->right = buildTree(rightPreorder,rightInorder);
        return root;
    }
};

09. 用两个栈实现队列

我的题解

class CQueue {
    
public:
    stack<int> que1;
    stack<int> que2;

    CQueue() {
    
        
    }
    
    void appendTail(int value) {
    
        que1.push(value);
    }
    
    int deleteHead() {
    
        int result = -1;
        while(que1.size() != 0){
    
            que2.push(que1.top());
            if(que1.size() == 1){
    
                result = que1.top();
                que2.pop();
            } 
            que1.pop();
        }
        while(que2.size() != 0){
    
            que1.push(que2.top());
            que2.pop();
        }
        return result;
    }
};

/** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */