题解 | #求二叉树的层序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> w;
        if (root==nullptr) return w;
        queue<TreeNode*>tree;
        tree.push(root);
        while (!tree.empty()) {
            vector<int> v;
            int size = tree.size();
            while (size--) {
                root = tree.front();
                tree.pop();
                v.push_back(root->val);
                if (root->left) tree.push(root->left);
                if (root->right) tree.push(root->right);

            }
            w.push_back(v);

        }
        return w;
    }
};

层次遍历，顺序为根节点，左节点，右节点。左节点得左节点、右节点。首先对根节点判断是否为空。 如果不为空，根节点入队。这是第一层，加入vector容器中，使用size来记录队的长度。什么情况下入队？当前队首元素的左孩子存在则入队左孩子，右孩子存在再入队右孩子。对第二层来说，队首第一个节点是第二层最左边的节点。层次遍历要把所有的一层都遍历完才到下一层。那么也就是说，我需要把这一层，每一个节点的左孩子节点和右孩子节点都判断一下处理入队操作。这样出队的时候顺序就是层次遍历的顺序，但是需要注意每一层都要放在一个vector中。