103. Binary Tree Zigzag Level Order Traversal
103. 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:
![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)
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
题目大意
按照 Z 字型层序遍历一棵树。
解题思路
这题和 第 102 题 二叉树的层序遍历 几乎是一样的,只要根据层数控制遍历方向即可。
代码
广度优先遍历(BFS)
// 思路一:广度优先遍历(BFS)
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function (root) {
let res = [];
if (root == null) return res;
let queue = [root];
let flag = true;
while (queue.length) {
let len = queue.length;
let temp = [];
for (let i = 0; i < len; i++) {
if (queue[i].left) queue.push(queue[i].left);
if (queue[i].right) queue.push(queue[i].right);
if (flag) {
temp.push(queue[i].val);
} else {
temp.unshift(queue[i].val);
}
}
flag = !flag;
queue = queue.slice(len);
res.push(temp);
}
return res;
};
深度优先遍历(DFS)
// 思路二:深度优先遍历(DFS)
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var zigzagLevelOrder = function (root) {
let res = [];
const traverse = (node, deep) => {
if (node == null) return;
if (res.length == deep) {
res[deep] = [node.val];
} else if (deep % 2 == 0) {
res[deep].push(node.val);
} else {
res[deep].unshift(node.val);
}
traverse(node.left, deep + 1);
traverse(node.right, deep + 1);
};
traverse(root, 0);
return res;
};