?劍指 Offer 32 - I. 從上到下打印二叉樹
難度：中等
從上到下打印出二叉樹的每個節(jié)點，同一層的節(jié)點按照從左到右的順序打印。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
節(jié)點總數(shù) <= 100
??思路：BFS
- 使用優(yōu)先隊列進行層序遍歷即可！
??代碼：(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;
}
}
?? 運行結(jié)果：
?? 復(fù)雜度分析：
-
時間復(fù)雜度：
O
(
n
)
O(n)
O(n)，其中
n為根為root的節(jié)點數(shù)。 - 空間復(fù)雜度： O ( n ) O(n) O(n)。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-621607.html
放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-621607.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(樹) 劍指 Offer 32 - I. 從上到下打印二叉樹 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
