二叉树层序遍历(基本版)🌟🌟🌟🌟🌟中等
课后作业
问题描述
原文链接：剑指 Offer 32 – I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
代码实现
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null){
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
res.add(temp.val);
if(temp.left != null){
queue.add(temp.left);
}
if(temp.right != null){
queue.add(temp.right);
}
}
int[] arr = new int[res.size()];
for(int i = 0; i < res.size(); i++){
arr[i] = res.get(i);
}
return arr;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
queue = [root]
res = []
while queue:
temp = queue.pop(0)
res.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
return res
C++
/**
* 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<int> levelOrder(TreeNode* root) {
if (!root) {
return {};
}
queue<TreeNode*> q;
vector<int> res;
q.push(root);
while (!q.empty()) {
TreeNode* temp = q.front();
q.pop();
res.push_back(temp->val);
if (temp->left) {
q.push(temp->left);
}
if (temp->right) {
q.push(temp->right);
}
}
return res;
}
};
Go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) []int {
if root == nil {
return []int{}
}
queue := []*TreeNode{root}
res := []int{}
for len(queue) > 0 {
temp := queue[0]
queue = queue[1:]
res = append(res, temp.Val)
if temp.Left != nil {
queue = append(queue, temp.Left)
}
if temp.Right != nil {
queue = append(queue, temp.Right)
}
}
return res
}
