优门设 网站,网站代理 正规备案,在百度上怎么建立网站,网站手机端跳转页面模板❓剑指 Offer 32 - II. 从上到下打印二叉树 II
难度#xff1a;简单
从上到下按层打印二叉树#xff0c;同一层的节点按从左到右的顺序打印#xff0c;每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回其层次遍历结果#xff1a…❓剑指 Offer 32 - II. 从上到下打印二叉树 II
难度简单
从上到下按层打印二叉树同一层的节点按从左到右的顺序打印每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回其层次遍历结果
[[3],[9,20],[15,7]
]提示
节点总数 1000
注意本题与 102. 二叉树的层序遍历 相同。
思路BFS
这里借助 优先队列 来实现 广度优先遍历
由于需要访问每一层的节点而且这一层访问才可以访问下一层, 所以另设一个计数变量 cnt 每访问一层都要先记录此时队列中有多少元素即为该层有多少个数。 每访问队列中一个元素就就 cnt-- 当 cnt 等于 0 时则该层数据访问完毕。 在结点出队时如果其左右子结点不为空时则将子节点入队。直到 优先队列 为空时结束。
代码(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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint ans;if(root nullptr) return ans;queueTreeNode* q;q.push(root);while(!q.empty()){int cnt q.size();vectorint temp;while(cnt-- 0){TreeNode* cur q.front();q.pop();temp.push_back(cur-val);if(cur-left ! nullptr) q.push(cur-left);if(cur-right ! nullptr) q.push(cur-right);}ans.push_back(temp);}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 ListListInteger levelOrder(TreeNode root) {ListListInteger ans new ArrayListListInteger();if(root null) return ans;QueueTreeNode q new LinkedList();q.add(root);while(!q.isEmpty()){int cnt q.size();ArrayListInteger temp new ArrayList();while(cnt-- 0){TreeNode cur q.poll();temp.add(cur.val);if(cur.left ! null) q.add(cur.left);if(cur.right ! null) q.add(cur.right);}ans.add(temp);}return ans;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 为树上所有节点的个数每个点进队出队各一次故渐进时间复杂度为 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)队列中元素的个数不超过 n 个故渐进空间复杂度为 O ( n ) O(n) O(n)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
