(Template) 102. Binary Tree Level Order Traversal

 Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

How to traverse the tree

There are two general strategies to traverse a tree:

• Depth First Search (DFS)

  In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

  The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.

• Breadth First Search (BFS)

  We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

Here the problem is to implement split-level BFS traversal : [[1], [2, 3], [4, 5]].

	/**
	* 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>> ans;
	queue<TreeNode*> q;
	if (root) {
	q.push(root);
	}
	TreeNode* cur;
	while (!q.empty()) {
	int size = q.size();
	ans.push_back(vector<int>());
	for (int i = 0; i < size; ++i) { // traverse nodes in the same level
	cur = q.front();
	q.pop();
	ans.back().push_back(cur->val); // visit the root
	if (cur->left) {
	q.push(cur->left); // push left child to queue if it is not null
	}
	if (cur->right) {
	q.push(cur->right); // push right child to queue if it is not null
	}
	}
	}
	return ans;
	}
	};

view raw 102. Binary Tree Level Order Traversal.cpp hosted with ❤ by GitHub