【代码随想录day 12】 力扣 102.107.199. 二叉树的层序遍历

视频讲解：https://www.bilibili.com/video/BV1GY4y1u7b2/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_637-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%B9%B3%E5%9D%87%E5%80%BC
力扣题目：https://leetcode.cn/problems/binary-tree-level-order-traversal/
https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
https://leetcode.cn/problems/binary-tree-right-side-view/

关于二叉树的层序遍历，需要用到队列这一数据结构，当遍历到一层时，将这一层节点的左节点和右节点压入队列中，然后下一次循环中弹出一个父节点再压入两个子节点，要注意que.size()是随着层数不断变化的。
假设又有个15个元素的4层二叉树

               1
            /     \
          2         3
        /  \       /  \
      4     5     6     7
     / \   / \   / \   / \
    8  9  10 11 12 13 14 15

那么每一次循环的队列元素如下所示：

1
23//1弹出，加入左右节点23
345//2弹出，加入左右节点45
4567//3弹出，加入左右节点67
56789
67891011
...

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode *> que;
        if(root!=NULL)
            que.push(root);
        vector<vector<int>> result;
        while(!que.empty())
        {
            int size = que.size();
            //printf("%d\n",size);
            vector<int> vec;
            for(int i=0;i<size;i++)
            {
                TreeNode *node=que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

107. 二叉树的层序遍历 II这一题与其类似，只不过要求从下网上遍历，我们只需要将上一题的结果反转即可。

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

109. 二叉树的右视图，这一题要求只返回最右边的元素，我们判断便利的元素是否为本行最后一个元素即可。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode *> que;
        if(root!=NULL) que.push(root);
        vector<int> result;
        while(!que.empty())
        {
            int size= que.size();
            for(int i=0;i<size;i++)
            {
                TreeNode *node=que.front();
                que.pop();
                //如果是这一行最后一个元素，就存进去
                if(i==size-1) result.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return result;

    }
};