【代碼隨想錄】day13

day13 二叉樹1

二叉樹定義

鏈?zhǔn)酱鎯?chǔ)的二叉樹節(jié)點(diǎn)的定義方式：

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

144.二叉樹的前序遍歷

方法一、遞歸法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        res.push_back(node->val);
        traversal(res, node->left);
        traversal(res, node->right);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

方法二、迭代法：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root == nullptr) {
            return res;
        }
        st.push(root);
        while (!st.empty()) {
            int n = st.size();
            while (n --) {
                TreeNode *node = st.top();
                st.pop();
                res.push_back(node->val);
                if (node->right) {
                    st.push(node->right);
                }
                if (node->left) {
                    st.push(node->left);
                }
            }
        }
        return res;
    }
};

145.二叉樹的后序遍歷

遞歸法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        traversal(res, node->left);
        traversal(res, node->right);
        res.push_back(node->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

迭代法：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            int n = st.size();
            while (n --) {
                TreeNode *node = st.top();
                st.pop();
                res.push_back(node->val);
                if (node->left) {
                    st.push(node->left);
                }
                if (node->right) {
                    st.push(node->right);
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

94.二叉樹的中序遍歷

遞歸法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        traversal(res, node->left);
        res.push_back(node->val);
        traversal(res, node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

迭代法：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> st;
        TreeNode *cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

102.二叉樹的層序遍歷

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            vector<int> temp;
            int n = q.size();
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

107.二叉樹的層次遍歷II

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> temp;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(temp);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

199.二叉樹的右視圖

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size() - 1;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            TreeNode *addNode = q.front();
            q.pop_front();
            res.push_back(addNode->val);
            if (addNode->left) {
                q.push_back(addNode->left);
            }
            if (addNode->right) {
                q.push_back(addNode->right);
            }
        }
        return res;
    }
};

637.二叉樹的層平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            double num = 0;
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                TreeNode *node = q.front();
                q.pop_front();
                num += node->val;
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(num / n);
        }
        return res;
    }
};

429.N叉樹的層序遍歷

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<Node*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> temp;
            while (n --) {
                Node *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                vector<Node*> ch = node->children;
                for (int i = 0; i < ch.size(); i ++) {
                    q.push_back(ch[i]);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

515.在每個(gè)樹行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int max_num = INT_MIN;
            int n = q.size();
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                max_num = node->val > max_num ? node->val : max_num;
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(max_num);
        }
        return res;
    }
};

116.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        deque<Node*> q;
        if (root->left) {
            q.push_back(root->left);
        }
        if (root->right) {
            q.push_back(root->right);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n --) {
                Node* node = q.front();
                q.pop_front();
                if (n > 0) {
                    node->next = q.front();
                }
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return root;
    }
};

117.填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針I(yè)I

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        deque<Node*> q;
        if (root->left) {
            q.push_back(root->left);
        }
        if (root->right) {
            q.push_back(root->right);
        }
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                Node *node = q.front();
                q.pop_front();
                if (i < n - 1) {
                    node->next = q.front();
                }
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return root;
    }
};

104.二叉樹的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

111.二叉樹的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        if (root->left == nullptr) {
            return 1 + minDepth(root->right);
        }
        if (root->right == nullptr) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容