“Algorithm Clearance Village-It turns out to be so simple”
Understanding level-order traversal
We have a binary tree, how do we traverse it layer by layer?
We need to borrow a data structure to traverse, and the data structure is a queue. We first put the root node into the queue and then traverse from there. How to traverse? Use a while loop to traverse, and the traversal will end when the queue is empty.
Let’s take a look at the key code and let’s go on:
class TreeNode{<!-- -->
int val;
TreeNode left;
TreeNode right;
public static void bianli(TreeNode root){<!-- -->
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
int size = queue.size();
for(int i=00;i<size;i + + ){<!-- -->
TreeNode temp = queue.remove();
if(temp.left != null){<!-- -->
queue.offer(temp.left);
}
if(temp.right != null){<!-- -->
queue.offer(temp.right);
}
}
}
}
}
In a while loop, we first get the size of the queue at this time. In fact, the size at this time is the number of elements in this layer. We need to process them one after another, and then add the elements in the next layer to the tail of the queue. . The for loop in the middle is to process the elements of one layer, and the if of the for loop is to add the elements of the next layer to the queue.
Through such a process we can achieve layer-order traversal.
Understand the questions
LeetCode102
Question requirement: Given a binary tree, please return the node values obtained by traversing it in layer order. (That is, visit all nodes layer by layer, from left to right).
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: []
Solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
*TreeNode left;
*TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
import java.util.LinkedList;
class Solution {<!-- -->
public List<List<Integer>> levelOrder(TreeNode root) {<!-- -->
if(root == null){<!-- -->
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
TreeNode t = root;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(t);
while(queue.size()> 0){<!-- -->
int size = queue.size();
List<Integer> tmp = new ArrayList<Integer>();
for(int i = 0 ; i< size;i + + ){<!-- -->
TreeNode temp = queue.remove();
tmp.add(temp.val);
if(temp.left != null){<!-- -->
queue.add(temp.left);
}
if(temp.right!=null){<!-- -->
queue.add(temp.right);
}
}
res.add(tmp);
}
return res;
}
}
Level-order traversal of binary trees II
Give you the root node root of the binary tree, and return its node value Bottom-up level order traversal. (That is, traverse from left to right layer by layer from the layer where the leaf node is to the layer where the root node is)
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]] Example 2: Input: root = [1] Output: [[1]] Example 3: Input: root = [] Output: []
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
*TreeNode left;
*TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {<!-- -->
public List<List<Integer>> levelOrderBottom(TreeNode root) {<!-- -->
List<List<Integer>> res = new LinkedList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null){<!-- -->
return new LinkedList<List<Integer>>();
}
queue.offer(root);
while(!queue.isEmpty()){<!-- -->
int size = queue.size();
List<Integer> temp = new ArrayList<Integer>();
for(int i = 0 ;i<size;i + + ){<!-- -->
TreeNode t = queue.poll();
temp.add(t.val);
if(t.left !=null){<!-- -->
queue.offer(t.left);
}
if(t.right != null){<!-- -->
queue.offer(t.right);
}
}
res.add(0,temp);
}
return res;
}
}
Zigzag level-order traversal of binary trees
Given the root node root of a binary tree, return the Zigzag level-order traversal of its node values. (That is, first traverse the next layer from left to right, then from right to left, and so on, alternating between layers)
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] Example 2: Input: root = [1] Output: [[1]] Example 3: Input: root = [] Output: []
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
*TreeNode left;
*TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {<!-- -->
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {<!-- -->
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(root == null){<!-- -->
return new LinkedList<List<Integer>>();
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
Boolean isleft = true;
while(!queue.isEmpty()){<!-- -->
Deque<Integer> temp = new LinkedList<Integer>();
int size = queue.size();
for(int i = 0 ; i< size;i + + ){<!-- -->
TreeNode t = queue.remove();
if(isleft){<!-- -->
temp.offerLast(t.val);
}else{<!-- -->
temp.offerFirst(t.val);
}
if(t.left != null){<!-- -->
queue.offer(t.left);
}
if(t.right != null){<!-- -->
queue.offer(t.right);
}
}
res.add(new LinkedList<Integer>(temp));
isleft = !isleft;
}
return res;
}
}
429,515,637 are all similar questions, just a few simple changes.
Find the value in the lower left corner of the tree
Given the root node root of a binary tree, please find the value of the bottommost leftmost node of the binary tree.
Assume there is at least one node in the binary tree.
Example 1:
Input: root = [2,1,3] Output: 1
Example 2:
Input: [1,2,3,4,null,5,6,null,null,7] Output: 7
One idea is to reverse it and then at the end, the last element in the queue is what we are looking for.
It’s not easy to understand. Let’s draw a picture to understand;
In this binary tree, what we are looking for is 2
To find the leftmost element of the last layer, we only need to invert, that is, let the node enter every time
When queuing, let the right one enter first, and then the last node is the node we are looking for.
Code solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
*TreeNode left;
*TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {<!-- -->
public int findBottomLeftValue(TreeNode root) {<!-- -->
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode temp = new TreeNode();
while(!queue.isEmpty()){<!-- -->
temp =queue.poll();
if(temp.right!= null){<!-- -->
queue.offer(temp.right);
}
if(temp.left!=null){<!-- -->
queue.offer(temp.left);
}
}
return temp.val;
}
}
Click the link: I am discussing interesting topics with my friends in “Programming Navigation”, would you like to get up?
You can also add me on QQ (2837468248) for consultation and explain your intention!