Links

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

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

题目描述

和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[][]}
*/
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.
    当前层次为偶数时,将当前节点放到当前层的结果数组尾部
  2. 2.
    当前层次为奇数时,将当前节点放到当前层的结果数组头部
  3. 3.
    递归对左子树进行之字形遍历,层数参数为当前层数+1
  4. 4.
    递归对右子树进行之字形遍历,层数参数为当前层数+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);
}
};

相关题目