【代码随想录】day13

day13 二叉树1

二叉树定义

链式存储的二叉树节点的定义方式：

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.在每个树行中找最大值

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.填充每个节点的下一个右侧节点指针

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.填充每个节点的下一个右侧节点指针II

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));
    }
};
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容