0103. 二叉树的锯齿形层次遍历 · ttttt

# 0103. 二叉树的锯齿形层次遍历 ## 题目地址(103. 二叉树的锯齿形层次遍历) <https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/> ## 题目描述和leetcode 102 基本是一样的，思路是完全一样的。 ``` <pre class="calibre18">``` 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层次遍历如下： [ [3], [20,9], [15,7] ] ``` ``` ## 前置知识 - 队列 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路这道题可以借助`队列`实现，首先把root入队，然后入队一个特殊元素Null(来表示每层的结束)。然后就是while(queue.length), 每次处理一个节点，都将其子节点（在这里是left和right）放到队列中。然后不断的出队，如果出队的是null，则表式这一层已经结束了，我们就继续push一个null。 ## 关键点解析 - 队列 - 队列中用Null(一个特殊元素)来划分每层 - 树的基本操作- 遍历 - 层次遍历（BFS） ## 代码 - 语言支持：JS，C++ JavaScript Code： ``` <pre class="calibre18">``` /** * @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： ``` <pre class="calibre18">``` /** * 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. 当前层次为偶数时，将当前节点放到当前层的结果数组尾部 2. 当前层次为奇数时，将当前节点放到当前层的结果数组头部 3. 递归对左子树进行之字形遍历，层数参数为当前层数+1 4. 递归对右子树进行之字形遍历，层数参数为当前层数+1 ### C++实现 ``` <pre class="calibre18">``` 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](102.binary-tree-level-order-traversal.html) - [104.maximum-depth-of-binary-tree](104.maximum-depth-of-binary-tree.html)