Question
Formatted question description: https://leetcode.ca/all/102.html
102 Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
@tag-tree
Algorithm
The typical breadth-first search BFS application, but here is a little more complicated, to separate the numbers of each layer and store them in a two-dimensional vector.
The general idea is basically the same, create a queue, and then put the root node first Go in, then find the left and right child nodes of the root node, then remove the root node.
At this time, the elements in the queue are all the nodes in the next layer. Use a for loop to traverse them, and then store them in a one-dimensional vector to traverse After that, save the one-dimensional vector into the two-dimensional vector
Note
Use the null
insertion method to mark each layer, is one way of marking level ending.
Pay attention to below:
-
The boundary problem of null, eg has only one root=1. Whenever it encounters null, first check whether q is empty. If q is empty, it will be the last, break directly If q is not empty, then offer a null as the end sign of the next layer
-
Note that the implementation of queue uses linkedlist, but arraylist does not work (removeFirst, removeLast are not supported)
Code
Java
-
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Binary_Tree_Level_Order_Traversal { public static void main(String[] args) { } /** Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } */ class Solution_countAsMarker { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (root == null) { return result; } // @note: use level count as marker of each level, instead of adding an extra null as marker int currentLevelCount = 0; int nextLevelCount = 0; // initialization Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); currentLevelCount++; List<Integer> currentLevelList = new ArrayList<>(); while (!q.isEmpty()) { TreeNode currentNode = q.poll(); currentLevelCount--; currentLevelList.add(currentNode.val); // enqueue if (currentNode.left != null) { q.offer(currentNode.left); nextLevelCount++; } if (currentNode.right != null) { q.offer(currentNode.right); nextLevelCount++; } // check if end of current level if (currentLevelCount == 0) { currentLevelCount = nextLevelCount; nextLevelCount = 0; // add this level int list to result result.add(new ArrayList<>(currentLevelList)); currentLevelList.clear(); } } return result; } } public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<List<Integer>>(); if (root == null) { return list; } Queue<TreeNode> sk = new LinkedList<>(); sk.offer(root); sk.offer(null);// @note: use null as marker for end of level List<Integer> oneLevel = new ArrayList<>(); while (!sk.isEmpty()) { TreeNode current = sk.poll(); if (current == null) { List<Integer> copy = new ArrayList<>(oneLevel); list.add(copy); // clean after one level recorded oneLevel.clear();// @memorize: this api // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping // sk.offer(null); // add marker if (!sk.isEmpty()) { sk.offer(null); // add marker } continue; } oneLevel.add(current.val); // @note:@memorize: since using null as marker, then must avoid adding null when children are null // sk.offer(current.left); // sk.offer(current.right); if (current.left != null) { sk.offer(current.left); } if (current.right != null) { sk.offer(current.right); } } return list; } } }
-
// OJ: https://leetcode.com/problems/binary-tree-level-order-traversal/ // Time: O(N) // Space: O(N) class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) return {}; vector<vector<int>> ans; queue<TreeNode*> q{ {root} }; while (q.size()) { ans.emplace_back(); for (int cnt = q.size(); cnt--; ) { auto n = q.front(); q.pop(); ans.back().push_back(n->val); if (n->left) q.push(n->left); if (n->right) q.push(n->right); } } return ans; } };
-
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution(object): def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] ans = [[root.val]] queue = deque([root]) while queue: levelans = [] for _ in range(0, len(queue)): root = queue.popleft() if root.left: levelans.append(root.left.val) queue.append(root.left) if root.right: levelans.append(root.right.val) queue.append(root.right) if levelans: ans.append(levelans) return ans