题目地址:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
题目描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
题目示例
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回:
[3,9,20,15,7]
解题思路
二叉树层次遍历选择广度优先搜索,而广度优先搜索一般采用队列实现。
程序源码
case1
/** * 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 == nullptr) return {}; vector<int> res; queue<TreeNode* > que; que.push(root); while(!que.empty()) { TreeNode* p = que.front(); que.pop(); res.push_back(p->val); if(p->left != nullptr) que.push(p->left); if(p->right != nullptr) que.push(p->right); } return res; } };
case2:
/** * 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 == nullptr) return {}; vector<int> res; queue<TreeNode*> q; q.push(root); while(!q.empty()) { int level_node = q.size(); for(int i = 0; i < level_node; i++) { TreeNode* node = q.front(); res.push_back(node->val); q.pop(); if(node->left != nullptr) q.push(node->left); if(node->right != nullptr) q.push(node->right); } } return res; } };