Skip to content

Latest commit

 

History

History
183 lines (143 loc) · 4.59 KB

103.binary-tree-zigzag-level-order-traversal.md

File metadata and controls

183 lines (143 loc) · 4.59 KB

题目地址(103. 二叉树的锯齿形层次遍历)

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

题目描述

和leetcode 102 基本是一样的，思路是完全一样的。

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 例如： 给定二叉树 [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：

/** * @param {TreeNode} root * @return {number[][]} */varzigzagLevelOrder=function(root){if(!root)return[];constitems=[];letisOdd=true;letlevelNodes=[];constqueue=[root,null];while(queue.length>0){constt=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);}}}returnitems};

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) {} * };*/classSolution { 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++实现

classSolution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { auto ret = vector<vector<int>>(); zigzagLevelOrder(root, 0, ret); return ret; } private:voidzigzagLevelOrder(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); } };

相关题目

close