5.二叉树

pptg大约 3 分钟

LeetCode.144.前序遍历open in new window

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> anss;
        travel(root, &anss);
        return anss;
    }

    void travel(TreeNode* root, vector<int> *vec){
        if(root == nullptr) return;
        vec->push_back(root->val);
        travel(root->left,vec);
        travel(root->right,vec);
        return;
    }
};

LeetCode.94.中序遍历open in new window

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> anss;
        travel(root, &anss);
        return anss;
    }

    void travel(TreeNode* root, vector<int> *vec){
        if(root == nullptr) return;
        travel(root->left,vec);
        vec->push_back(root->val);
        travel(root->right,vec);
        return;
    }
};

LeetCode.145.后序遍历open in new window

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> anss;
        travel(root, &anss);
        return anss;
    }

    void travel(TreeNode* root, vector<int> *vec){
        if(root == nullptr) return;
        travel(root->left,vec);
        travel(root->right,vec);
        vec->push_back(root->val);
        return;
    }
};

LeetCode.102.二叉树的层序遍历open in new window

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> anss;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> vec;
            for(int i = 0;i < size;i++){
                TreeNode *n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                vec.push_back(n->val);
            }
            anss.push_back(vec);
        }
        return anss;
    }
};

LeetCode.107.二叉树层序遍历IIopen in new window

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> anss;
        queue<TreeNode*> q;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> vec;
            for(int i = 0;i < size;i++){
                TreeNode *n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                vec.push_back(n->val);
            }
            anss.push_back(vec);
        }
        reverse(anss.begin(),anss.end());
        return anss;
    }
};

LeetCode.199.二叉树右视图open in new window

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> anss;
        queue<TreeNode*> q;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                TreeNode *n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                if(i == size-1){
                    anss.push_back(n->val);
                }
            }
        }
        return anss;
    }
};

LeetCode.637.二叉树的层平均值open in new window

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> q;
        vector<double> anss;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            long long summ = 0;
            for(int i = 0;i < size;i++){
                TreeNode* n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                summ += n->val;
            }
            anss.push_back((double)summ/(double)size);
        }
        return anss;
    }
};

LeetCode.429.N叉树的层序遍历open in new window

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> q;
        vector<vector<int>> anss;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> vec;
            for(int i = 0;i < size;i++){
                Node* n = q.front();
                q.pop();
                for(int j = 0;j < n->children.size();j++){
                    if(n->children[j]) q.push(n->children[j]);
                }
                vec.push_back(n->val);
            }
            anss.push_back(vec);
        }
        return anss;
    }
};

LeetCode.515.在每个树行中找最大值open in new window

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> anss;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            int maxx = -INT_MAX-1;
            for(int i = 0;i < size;i++){
                TreeNode* n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                maxx = max(maxx,n->val);
            }
            anss.push_back(maxx);
        }
        return anss;
    }
};

LeetCode.116.填充每个节点的下一个右侧节点指针open in new window

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> q;
        vector<int> anss;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            Node* pre = q.front();
            for(int i = 0;i < size;i++){
                Node* n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                if(i > 0){
                    pre->next = n;
                    pre = n;
                }
            }
        }
        return root;
    }
};

LeetCode.117.填充每个节点的下一个右侧节点指针IIopen in new window

class Solution {
public:
    Node* connect(Node* root) {
                queue<Node*> q;
        vector<int> anss;
        if(root != NULL) q.push(root);
        while(!q.empty()){
            int size = q.size();
            Node* pre = q.front();
            for(int i = 0;i < size;i++){
                Node* n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
                if(i > 0){
                    pre->next = n;
                    pre = n;
                }
            }
        }
        return root;
    }
};

LeetCode.104.二叉树的最大深度open in new window

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int anss = 0;
        queue<TreeNode*> q;
        if(root != NULL){
            q.push(root);
        }
        while(!q.empty()){
            int size = q.size();
            anss++;
            for(int i = 0;i < size;i++){
                TreeNode* n = q.front();
                q.pop();
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
            }
        }
        return anss;
    }
};

LeetCode.111.二叉树的最小深度open in new window

class Solution {
public:
    int minDepth(TreeNode* root) {
        int anss = 0;
        queue<TreeNode*> q;
        if(root != NULL){
            q.push(root);
        }
        while(!q.empty()){
            int size = q.size();
            anss++;
            for(int i = 0;i < size;i++){
                TreeNode* n = q.front();
                q.pop();
                if(!n->left && !n->right){
                    return anss;
                }
                if(n->left) q.push(n->left);
                if(n->right) q.push(n->right);
            }
        }
        return anss;
    }
};