This is the 28th day of my participation in the August Text Challenge.More challenges in August
Serrated sequence traversal of binary trees
Given a binary tree, return a zigzag sequence traversal of its node values. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).
Examples can be found on the LeetCode website.
Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Solution 1: use queues and stacks to traverse the binary tree
Queue is characterized by first-in, first-out, and stack is characterized by last-in, first-out. Therefore, queue and stack are used to traverse binary tree to achieve sawtooth traversal, and the specific process is as follows:
- First, if root is empty, return the empty List.
- If root is not empty, declare a queue of Nodes, add root to the queue, declare a result, and declare a Boolean variable directionFlag. When directionFlag is true, add nodes to the stack from left to right. When directionFlag is false, insert nodes from right to left and iterate over nodes as follows:
- First, the number of nodes in the current queue (that is, the number of nodes in the current tier) is recorded with count, with vals recording the value of the current node, and a stack, temp, is declared;
- If the left and right child nodes of the current node are not empty, determine whether to put them into Temp from left to right or from right to left according to directionFlag. Add vals to the result result.
- Remove all elements from the stack temp and place them in Nodes.
- Repeat through the nodes in Nodes until Nodes is empty.
- Finally, result is the result of serrated sequence traversal.
** Solution is similar to leetcode-102-binary tree sequence traversal.
import java.util.*;
public class LeetCode_103 {
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> nodes = new LinkedList<>();
nodes.add(root);
// Add nodes from left to right when directionFlag is true; When directionFlag is false, add nodes from right to left
boolean directionFlag = true;
while(! nodes.isEmpty()) {int count = nodes.size();
List<Integer> vals = new ArrayList<>();
Stack<TreeNode> temp = new Stack<>();
while (count > 0) {
TreeNode curNode = nodes.poll();
vals.add(curNode.val);
if(! directionFlag) {if(curNode.right ! =null) {
temp.push(curNode.right);
}
if(curNode.left ! =null) { temp.push(curNode.left); }}else {
if(curNode.left ! =null) {
temp.push(curNode.left);
}
if(curNode.right ! =null) {
temp.push(curNode.right);
}
}
count--;
}
// Put the stack node into the queue
while(! temp.isEmpty()) { nodes.add(temp.pop()); }// Change the order after each layerdirectionFlag = ! directionFlag; result.add(vals); }return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.right = new TreeNode(5);
for (List<Integer> integers : zigzagLevelOrder(root)) {
for (Integer integer : integers) {
System.out.print(integer + ""); } System.out.println(); }}}Copy the code
Complacency is the enemy of study. If you want to learn something seriously, you must never start with complacency.