Tree5

发表于 分类于 ，

题目描述[原题描述][https://leetcode-cn.com/problems/binary-tree-level-order-traversal/]

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

算法描述

​ 层次遍历就是将层的节点值存入列表中返回即可，在这里会用到队列结构queue,将根节点插入，每次遍历下一层的所有节点，直到队列为空，完成了层次遍历，需要注意的就是每次加入队列时需要判断当前节点是不是为空，为空就不进行插入操作；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> vec;
        if(root==NULL)return vec;
        que.push(root);
        vector<int> v;
        while(!que.empty()){
            v.clear();
           int len = que.size(); 
           for(int i=0;i<len;i++){
               TreeNode* node = que.front();
               que.pop();
               v.push_back(node->val);
               if(node->left)que.push(node->left);
               if(node->right)que.push(node->right);
           }
            vec.push_back(v);
        }
        return vec;
        
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)return ans;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(root);
        while(!que.isEmpty()){
            List<Integer> res = new ArrayList<Integer>();
            int len = que.size();
            for(int i=0;i<len;i++){
                TreeNode temp = que.poll();
                res.add(temp.val);
                if(temp.left!=null)que.offer(temp.left);
                if(temp.right!=null)que.offer(temp.right);
            }
            ans.add(res);
        }
        return ans;
    }
}