Algorithm
Problem Nmae: 103. Binary Tree Zigzag Level Order Traversal
problem Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
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: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int depth(struct TreeNode *node) {
int l, r;
if (!node) return 0;
l = depth(node->left) + 1;
r = depth(node->right) + 1;
if (l > r) return l;
return r;
}
#define PUSH(Q, L, N) do { Q[L ++] = N; } while (0)
int** zigzagLevelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int d, **p, *buff, *c, k;
struct TreeNode **queue, **tmp;
int qlen, tsz, tlen;
struct TreeNode *node;
*returnSize = 0;
if (!root) return NULL;
d = depth(root);
p = malloc(d * sizeof(int *));
c = malloc(d * sizeof(int));
//assert(p && c);
*returnSize = d;
d = 1;
queue = malloc(1 * sizeof(struct TreeNode *));
//assert(queue);
qlen = 0;
PUSH(queue, qlen, root);
tmp = NULL;
while (qlen) {
if (!tmp) {
tlen = 0;
tsz = 10;
tmp = malloc(tsz * sizeof(struct TreeNode *));
//assert(tmp);
k = 0;
buff = malloc(qlen * sizeof(int));
//assert(buff);
} else if (tsz < = tlen + 1) {
tsz *= 2;
tmp = realloc(tmp, tsz * sizeof(struct TreeNode *));
//assert(tmp);
}
node = queue[-- qlen];
buff[k ++] = node->val;
if ( (d % 2) && node->left) PUSH(tmp, tlen, node->left);
if ( node->right) PUSH(tmp, tlen, node->right);
if (!(d % 2) && node->left) PUSH(tmp, tlen, node->left);
if (qlen == 0) {
p[d - 1] = buff;
c[d - 1] = k;
d ++;
free(queue);
queue = tmp;
qlen = tlen;
tmp = NULL;
}
}
free(queue);
*columnSizes = c;
return p;
}
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector < vector<int>>res;
if(!root) return res;
deque < TreeNode*>cur, next;
cur.push_back(root);
vector<int>v;
int level = 0;
while(!cur.empty()){
auto p = cur.front();
cur.pop_front();
v.push_back(p->val);
if(p->left) next.push_back(p->left);
if(p->right) next.push_back(p->right);
if(cur.empty()){
if(level++ % 2) reverse(v.begin(), v.end());
res.push_back(v);
v.clear();
swap(cur, next);
}
}
return res;
}
};
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[20,9],[15,7]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
if (root == null) {
return ans;
}
Queue < TreeNode> queue = new LinkedList<>();
boolean leftToRight = true;
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List < Integer> temp = new ArrayList<>();
while (size-- > 0) {
TreeNode removed = queue.remove();
temp.add(removed.val);
if (removed.left != null) {
queue.add(removed.left);
}
if (removed.right != null) {
queue.add(removed.right);
}
}
if (!leftToRight) {
Collections.reverse(temp);
}
ans.add(temp);
leftToRight = !leftToRight;
}
return ans;
}
}
Input
root = [1]
Output
[[1]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const zigzagLevelOrder = function(root) {
if(root == null) return []
const row = [root]
const res = []
bfs(row, res)
for(let i = 0; i < res.length; i++) {
res[i] = i % 2 === 0 ? res[i] : res[i].reverse()
}
return res
};
function bfs(row, res) {
if(row.length === 0) return
let tmp = []
let next = []
for(let i = 0; i < row.length; i++) {
tmp.push(row[i].val)
if(row[i].left) {
next.push(row[i].left)
}
if(row[i].right) {
next.push(row[i].right)
}
}
if(tmp.length) {
res.push(tmp)
}
bfs(next, res>
}
Input
root = [1]
Output
[[1]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
q, i, res = [root], 0, []
while any(q):
add, q, i = q if i % 2 == 0 else q[::-1], [kid for node in q for kid in (node.left, node.right) if kid], i+1
res.append([item.val for item in add])
return res
Input
root = []
Output
[]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _103_BinaryTreeZigzagLevelOrderTraversal
{
private Queue < TreeNode> queue = new Queue();
public IList 0)
{
var levelSize = queue.Count;
var result = new int[levelSize];
for (int i = 0; i < levelSize; i++)
{
var node = queue.Dequeue();
result[leftToRight ? i : (levelSize - i - 1)] = node.val;
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
results.Add(result);
leftToRight = !leftToRight;
}
return results;
}
}
}
Input
root = []
Output
[]