❓剑指 Offer 32 - I. 从上到下打印二叉树
难度：中等
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3/ \9 20/ \15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 100
💡思路：BFS
- 使用优先队列进行层序遍历即可！
🍁代码：(C++、Java)
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) {vector<int> ans;if(root == nullptr) return ans;queue<TreeNode*> q;q.push(root);while(!q.empty()){TreeNode* temp = q.front();q.pop();ans.push_back(temp->val);if(temp->left != nullptr) q.push(temp->left);if(temp->right != nullptr) q.push(temp->right);}return ans;}
};
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) {ArrayList<Integer> ans = new ArrayList<>();if(root == null) return new int[0];Queue<TreeNode> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){TreeNode temp = q.poll();ans.add(temp.val);if(temp.left != null) q.add(temp.left);if(temp.right != null) q.add(temp.right);}int[] ret = new int[ans.size()];for(int i = 0; i < ans.size(); i++){ret[i] = ans.get(i);}return ret;}
}
🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)，其中
n为根为root的节点数。 - 空间复杂度： O ( n ) O(n) O(n)。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！
