103. Binary Tree Zigzag Level Order Traversal
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu duyệt cây nhị phân từng tầng (level order), nhưng xen kẽ hướng duyệt từng tầng: Tầng đầu từ trái sang phải, tầng tiếp theo từ phải sang trái, rồi lại trái sang phải
Approach
Time and space complexity
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function zigzagLevelOrder(root: TreeNode | null): number[][] {
16 if(!root) return [];
17 const res: number[][] = [];
18 const queue: TreeNode[] = [];
19 let left_to_right = true;
20 while(queue.length) {
21 const level_size = queue.length;
22 const level: number[] =[];
23 for(let i =0; i < level_size;i++) {
24 const node = queue.shift()!;
25 level.push(node.val);
26 if(node.left) queue.push(node.left)
27 if(node.right)queue.push(node.right);
28 }
29 if(!left_to_right) level.reverse();
30 res.push(level)
31 left_to_right = !left_to_right
32 }
33 return res
34};left_to_right