102. Binary Tree Level Order Traversal二叉树层序遍历

Dear 丶 2022-01-05 04:11 178阅读 0赞

网址：https://leetcode.com/problems/binary-tree-level-order-traversal/

参考：https://www.cnblogs.com/grandyang/p/4051321.html

二叉树的层次遍历的做法是维护一个队列，不断使节点入队，使用了val后即出队。结束标志是队列是否为空

主要难度在于要分别提取出每层的val

我们可把在树的一层节点全部入列后队列的长度作为for循环的判断依据

/**
     * 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:
        vector<vector<int>> levelOrder(TreeNode* root) {
            if (!root) 
                return {};
            vector<vector<int>> res;
            queue<TreeNode*> q;
            q.push(root);
            vector<int> oneLevel;
            while (!q.empty()) {
                oneLevel.clear();
                // 一轮for循环即是对一层节点的处理
                for (int i = q.size(); i > 0; --i) {
                    TreeNode *t = q.front();
                    q.pop();
                    oneLevel.push_back(t->val);
                    if (t->left)
                        q.push(t->left);
                    if (t->right)
                        q.push(t->right);
                }
                res.push_back(oneLevel);
            }
            return res;
        }
    };

![1209052-20190425212137145-979069029.png][]

转载于:https://www.cnblogs.com/tornado549/p/10771094.html

[1209052-20190425212137145-979069029.png]: /images/20211230/471261895d614f65aec36b388eb82138.png