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

题目：二叉树的层序遍历

描述：给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是[[3],[9,20],[15,7]]。

示例1：输入：{1,2}，返回值：[[1],[2]]

解法一：

思路分析：层序遍历，是将一个结点的左右节点，按照一层层的进行遍历，所以我们使用队列，先进先出，从根结点进行push到队列，如果第二层存在，就是队列出来的顺序，第二层每个执行的元素添加到队列当中，所以添加的所有结点在第二层的后面，假设pop遍历第n层的节点，每个节点会push左右两个节点进去。但是队列先进先出。它会放到队尾(下一层)。直到第n层的最后一个pop出来，第n+1层的还在队列中整齐排着，这就达到一个层序的效果。

实例分析：二叉树{3,9,20,#,#,15,7}

具体C++代码如下所示：

	/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector><>>
     */
    vector levelOrder(TreeNode* root) {
        // write code here
        vector res;//存放最终的结果值
        if(root == NULL)
            return res;
        queue<treenode> q;//定义队列
        q.push(root);//将根节点放进去
        while(!q.empty()){
            vector temp;//设立容器
            int n = q.size();//队列中容器的大小
            for(int i = 0; i < n;i++){ TreeNode* node = q.front();//第一个元素 
                q.pop(); 
                temp.push_back(node->val);//将第一层的值存放到容器当中
                if(node->left != NULL)
                    q.push(node->left);//将左子树放进去
                if(node->right != NULL)
                    q.push(node->right);//将右子树放进去
            }
            res.push_back(temp);
        }
        return res;
    }
};</treenode></vector>

解法二：

思路分析：在方法一中，我们已经明白了只要将队列中的值一层一层遍历完成，即先遍历第一层的元素，将当前层的元素遍历完成后，再次遍历下一层队列的元素即可完成最终操作。同样我们可以由层次遍历的单层循环变为双层循环，即将内层循环重新遍历一层也可以完成相应功能。

 import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<arraylist><>>
     */
    public ArrayList levelOrder (TreeNode root) {
        // write code here
        ArrayList res = new ArrayList<>();//创建一个链表，用于存储
        if(root == null )
            return res;
        LinkedList que = new LinkedList<>();
        que.offer(root);//用来插入指定的元素插入此优先级队列
        while(!que.isEmpty()){
            int len = que.size();
            ArrayListlist = new ArrayList<>();
            while(len > 0){
                TreeNode node = que.poll();//poll是队列数据结构实现类的方法，从队首获取元素，同时获取的这个元素将从原队列删除；
                list.add(node.val);
                if(node.left != null)
                    que.offer(node.left);
                if(node.right != null)
                    que.offer(node.right);
                len--;
            }
            res.add(list);
        }
        return res;
    }
} </arraylist>