title: 每日一练（19）：从上到下打印二叉树
categories:[剑指offer]
tags:[每日一练]
date: 2022/02/15
每日一练（19）：从上到下打印二叉树
从上到下按层打印二叉树，同一层的节点按从左到右的程序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3/ \9 20/ \15 7返回其档次遍历后果：
[ [3], [9,20], [15,7]]提醒：
节点总数 <= 1000
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
留神的是要把每一层放到一起，须要保护一个level进行保留。
DFS记得应用援用&，不然就得保护一个全局变量了。
办法一：BFS
/** * 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<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); vector<vector<int>> res; while (q.size()) { int size = q.size(); vector<int> level; for (int i=0;i<size;i++) { TreeNode* rt = q.front(); q.pop(); if (!rt) { continue; } level.push_back(rt->val); if (rt->left) { q.push(rt->left); } if (rt->right) { q.push(rt->right); } } if (level.size()!=NULL) { res.push_back(level); } } return res; }};办法二：DFS
/** * 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<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; dfs(root, res, 0); return res; } void dfs(TreeNode* root,vector<vector<int>>& res,int level) { if (!root) { return; } if (level >= res.size()) { res.emplace_back(vector<int>()); } res[level].emplace_back(root->val); dfs(root->left, res, level+1); dfs(root->right, res, level+1); }};