题目地址
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
题目描述
和leetcode 102 基本是一样的,思路是完全一样的。
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路
这道题可以借助队列
实现,首先把root入队,然后入队一个特殊元素Null(来表示每层的结束)。
然后就是while(queue.length), 每次处理一个节点,都将其子节点(在这里是left和right)放到队列中。
然后不断的出队, 如果出队的是null,则表式这一层已经结束了,我们就继续push一个null。
关键点解析
-
队列
-
队列中用Null(一个特殊元素)来划分每层
-
树的基本操作- 遍历 - 层次遍历(BFS)
代码
- 语言支持:JS,C++
JavaScript Code:
/* * @lc app=leetcode id=103 lang=javascript * * [103] Binary Tree Zigzag Level Order Traversal * * https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ * * algorithms * Medium (40.57%) * Total Accepted: 201.2K * Total Submissions: 493.7K * Testcase Example: '[3,9,20,null,null,15,7]' * * Given a binary tree, return the zigzag level order traversal of its nodes' * values. (ie, from left to right, then right to left for the next level and * alternate between). * * * For example: * Given binary tree [3,9,20,null,null,15,7], * * 3 * / \ * 9 20 * / \ * 15 7 * * * * return its zigzag level order traversal as: * * [ * [3], * [20,9], * [15,7] * ] * * */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ var zigzagLevelOrder = function(root) { if (!root) return []; const items = []; let isOdd = true; let levelNodes = []; const queue = [root, null]; while(queue.length > 0) { const t = queue.shift(); if (t) { levelNodes.push(t.val) if (t.left) { queue.push(t.left) } if (t.right) { queue.push(t.right) } } else { if (!isOdd) { levelNodes = levelNodes.reverse(); } items.push(levelNodes) levelNodes = []; isOdd = !isOdd; if (queue.length > 0) { queue.push(null); } } } return items };
C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { auto ret = vector<vector<int>>(); if (root == nullptr) return ret; auto queue = vector<const TreeNode*>{root}; auto isOdd = true; while (!queue.empty()) { auto sz = queue.size(); auto level = vector<int>(); for (auto i = 0; i < sz; ++i) { auto n = queue.front(); queue.erase(queue.begin()); if (isOdd) level.push_back(n->val); else level.insert(level.begin(), n->val); if (n->left != nullptr) queue.push_back(n->left); if (n->right != nullptr) queue.push_back(n->right); } isOdd = !isOdd; ret.push_back(level); } return ret; } };
拓展
由于二叉树是递归结构,因此,可以采用递归的方式来处理。在递归时需要保留当前的层次信息(从0开始),作为参数传递给下一次递归调用。
描述
- 当前层次为偶数时,将当前节点放到当前层的结果数组尾部
- 当前层次为奇数时,将当前节点放到当前层的结果数组头部
- 递归对左子树进行之字形遍历,层数参数为当前层数+1
- 递归对右子树进行之字形遍历,层数参数为当前层数+1
C++实现
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { auto ret = vector<vector<int>>(); zigzagLevelOrder(root, 0, ret); return ret; } private: void zigzagLevelOrder(const TreeNode* root, int level, vector<vector<int>>& ret) { if (root == nullptr || level < 0) return; if (ret.size() <= level) { ret.push_back(vector<int>()); } if (level % 2 == 0) ret[level].push_back(root->val); else ret[level].insert(ret[level].begin(), root->val); zigzagLevelOrder(root->left, level + 1, ret); zigzagLevelOrder(root->right, level + 1, ret); } };
相关题目
- 102.binary-tree-level-order-traversal
- 104.maximum-depth-of-binary-tree
题目地址 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to…
我的遍历遍历有什么问题? - java我正在尝试解决此问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/,即使用递归解决方案进行预遍历。编辑:整个代码:import java.util.ArrayList; import java.util.List; public class Solution { public …