The 102th question
Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right). For example: given a binary tree: [3.9.20.null.null.15.7].3
/ \
9 20
/ \
15 7Returns the result of its hierarchical traversal: [[3],
[9.20],
[15.7[LeetCode] [LeetCode] [LeetCode]//leetcode-cn.com/problems/binary-tree-level-order-traversal
Copy the codeHow do you traverse a tree
There are two common strategies for traversing a tree:
- Depth-first Search (DFS)
In this strategy, we use depth as a priority, so that we can start with the heel and reach a certain leaf, and then return to the root to reach another branch.
The depth-first search strategy can be subdivided into first-order traversal, middle-order traversal, and back-order traversal according to the relative order of the root node, left child, and right child.
- Width First search (BFS)
We visit the whole tree layer by layer in height order, and the higher-level nodes will be accessed before the lower-level nodes.
Their thinking
Method 1: Iteration + queue
We place the tree vertices in a hierarchical queue structure, and the elements in the queue comply with FIFO (first-in, first-out). Use the LinkedList implementation in the Queue interface.
The algorithm is as follows:
- The initialization queue contains only one node, root.
- When the queue is not empty, the loop begins:
- Calculates how many elements the current layer has: equal to the length of the queue
- The initial List variable subResult is used to hold the node value of the current tier
- Pop these elements from the queue and add their values to the subResult list
- Push their child node into the queue as the next tier
- Go to the next layer and add the current layer subResult to result
/** * search + queue */
class Solution102_1 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();
return BFS(root);
}
List<List<Integer>> BFS(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<List<Integer>> result = new LinkedList<>();
while(! queue.isEmpty()) {int size = queue.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
subResult.add(node.val);
}
result.add(subResult);
}
returnresult; }}Copy the codeMethod 2: Recurse
First, verify that the tree is not empty, and then call the recursive function DFS(node,result,level). The parameters are the current node, the return result list, and the node hierarchy.
The algorithm is as follows:
- The length of the result list is smaller than level. Add a new list for result
- Add node values for the result list of the current layer, i.e. Result.get (level-1).add(node.val)
- If there are left children, call DFS(node.left, result, level + 1) to enter recursion
- If there are right children, call DFS(node.right, result, level + 1) to enter recursion
/** * deep search + recursion */
class Solution102_2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<List<Integer>> result = new LinkedList<>();
DFS(root, result, 1);
return result;
}
void DFS(TreeNode node, List<List<Integer>> result, int level) {
if (result.size() < level) {
result.add(new LinkedList<>());
}
result.get(level - 1).add(node.val);
if(node.left ! =null) {
DFS(node.left, result, level + 1);
}
if(node.right ! =null) {
DFS(node.right, result, level + 1); }}}Copy the codeThe complete code
public class Sub102 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
Solution102_2 solution = new Solution102_2();
List<List<Integer>> list = solution.levelOrder(root);
for(List<Integer> subList : list) { System.out.println(subList.toString()); }}}/** * search + queue */
class Solution102_1 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();
return BFS(root);
}
List<List<Integer>> BFS(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<List<Integer>> result = new LinkedList<>();
while(! queue.isEmpty()) {int size = queue.size();
List<Integer> subResult = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
subResult.add(node.val);
}
result.add(subResult);
}
returnresult; }}/** * deep search + recursion */
class Solution102_2 {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
List<List<Integer>> result = new LinkedList<>();
DFS(root, result, 1);
return result;
}
void DFS(TreeNode node, List<List<Integer>> result, int level) {
if (result.size() < level) {
result.add(new LinkedList<>());
}
result.get(level - 1).add(node.val);
if(node.left ! =null) {
DFS(node.left, result, level + 1);
}
if(node.right ! =null) {
DFS(node.right, result, level + 1); }}}Copy the codedata
- The source address
- This article addresses
- LeetCode solution directory