103. Binary Tree Zigzag Level Order Traversal
leetcode medium
#csharp#graph#leetcode#medium#queue#search#tree#two-pointers
Task
Дан корень бинарного дерева. Верните обход узлов дерева по уровням в виде зигзага (то есть слева направо, затем справа налево для следующего уровня и чередуйте далее).
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
C# solution
matched/originalpublic class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
List<IList<int>> result = new List<IList<int>>();
if (root == null)
return result;
Queue<TreeNode> nodeQueue = new Queue<TreeNode>();
nodeQueue.Enqueue(root);
nodeQueue.Enqueue(null);
LinkedList<int> levelList = new LinkedList<int>();
bool isOrderLeft = true;
while (nodeQueue.Count > 0) {
TreeNode currentNode = nodeQueue.Dequeue();
if (currentNode != null) {
if (isOrderLeft)
levelList.AddLast(currentNode.val);
else
levelList.AddFirst(currentNode.val);
if (currentNode.left != null)
nodeQueue.Enqueue(currentNode.left);
if (currentNode.right != null)
nodeQueue.Enqueue(currentNode.right);
} else {
result.Add(new List<int>(levelList));
levelList.Clear();
if (nodeQueue.Count > 0)
nodeQueue.Enqueue(null);
isOrderLeft = !isOrderLeft;
}
}
return result;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public IList<vector<int>> ZigzagLevelOrder(TreeNode root) {
List<vector<int>> result = new List<vector<int>>();
if (root == null)
return result;
queue<TreeNode> nodeQueue = new queue<TreeNode>();
nodeQueue.Enqueue(root);
nodeQueue.Enqueue(null);
LinkedList<int> levelList = new LinkedList<int>();
bool isOrderLeft = true;
while (nodeQueue.size() > 0) {
TreeNode currentNode = nodeQueue.Dequeue();
if (currentNode != null) {
if (isOrderLeft)
levelList.AddLast(currentNode.val);
else
levelList.AddFirst(currentNode.val);
if (currentNode.left != null)
nodeQueue.Enqueue(currentNode.left);
if (currentNode.right != null)
nodeQueue.Enqueue(currentNode.right);
} else {
result.push_back(new List<int>(levelList));
levelList.Clear();
if (nodeQueue.size() > 0)
nodeQueue.Enqueue(null);
isOrderLeft = !isOrderLeft;
}
}
return result;
}
}Java solution
matched/originalclass Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> results = new ArrayList<List<Integer>>();
LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
node_queue.addLast(root);
node_queue.addLast(null);
LinkedList<Integer> level_list = new LinkedList<Integer>();
boolean is_order_left = true;
while (node_queue.size() > 0) {
TreeNode curr_node = node_queue.pollFirst();
if (curr_node != null) {
if (is_order_left) level_list.addLast(curr_node.val);
else level_list.addFirst(curr_node.val);
if (curr_node.left != null) node_queue.addLast(curr_node.left);
if (curr_node.right != null) node_queue.addLast(
curr_node.right
);
} else {
results.add(level_list);
level_list = new LinkedList<Integer>();
if (node_queue.size() > 0) node_queue.addLast(null);
is_order_left = !is_order_left;
}
}
return results;
}
}JavaScript solution
matched/originalvar zigzagLevelOrder = function (root) {
if (root === null) return [];
const results = [];
const node_queue = [root, null];
const level_list = [];
let is_order_left = true;
while (node_queue.length > 0) {
const curr_node = node_queue.shift();
if (curr_node !== null) {
if (is_order_left) level_list.push(curr_node.val);
else level_list.unshift(curr_node.val);
if (curr_node.left !== null) node_queue.push(curr_node.left);
if (curr_node.right !== null) node_queue.push(curr_node.right);
} else {
results.push([...level_list]);
level_list.length = 0;
if (node_queue.length > 0) node_queue.push(null);
is_order_left = !is_order_left;
}
}
return results;
};Python solution
matched/originalfrom collections import deque
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
ret = []
level_list = deque()
if root is None:
return []
node_queue = deque([root, None])
is_order_left = True
while len(node_queue) > 0:
curr_node = node_queue.popleft()
if curr_node:
if is_order_left:
level_list.append(curr_node.val)
else:
level_list.appendleft(curr_node.val)
if curr_node.left:
node_queue.append(curr_node.left)
if curr_node.right:
node_queue.append(curr_node.right)
else:
ret.append(level_list)
if len(node_queue) > 0:
node_queue.append(None)
level_list = deque()
is_order_left = not is_order_left
return retGo solution
matched/originalfunc zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var res [][]int
nodeQueue := []*TreeNode{root, nil}
levelList := []int{}
isOrderLeft := true
for len(nodeQueue) > 0 {
currNode := nodeQueue[0]
nodeQueue = nodeQueue[1:]
if currNode != nil {
if isOrderLeft {
levelList = append(levelList, currNode.Val)
} else {
levelList = append([]int{currNode.Val}, levelList...)
}
if currNode.Left != nil {
nodeQueue = append(nodeQueue, currNode.Left)
}
if currNode.Right != nil {
nodeQueue = append(nodeQueue, currNode.Right)
}
} else {
res = append(res, levelList)
levelList = []int{}
if len(nodeQueue) > 0 {
nodeQueue = append(nodeQueue, nil)
}
isOrderLeft = !isOrderLeft
}
}
return res
}Explanation
Algorithm
1️⃣
Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.
2️⃣
Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).
3️⃣
Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.
😎