2ba6be54c287e6bcb726648da1da8bef
(难度Medium) Problem 103. Binary Tree Zigzag Level Order Traversal(二叉树上做zigzag)

Binary Tree Zigzag Level Order Traversal

Difficulty

Medium

Description

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]
]

题意

这题的题意有点奇怪,在上一题的基础上稍稍做一些改动。上一题当中,我们需要将一棵二叉树上的所有元素按照所在的树深度归类。把树深度相同的元素按树上从左到右的顺序放在一起,最后返回树归类之后的结果。

在这一题当中,我们需要在这个结果上做一个zigzag操作。zigzag是蛇形的意思,其实可以简单理解成把树深度为奇数(树根深度看作0)的元素倒叙摆放。

题解

这题最简单的解法就是用上一题的代码获取归类之后的结果,然后遍历结果,将奇数位置的vector,通过调用reverse方法倒叙即可。基本上完全是上一题的代码,只需要增加三行,非常简单。

代码如下:

```c++
class Solution {
public:
void dfs(TreeNode* nd, vector> &rt, int level) {
if (nd == nullptr) return ;
if (level >= rt.size()) rt.push_back(vector());
// 中序遍历
dfs(nd->left, rt, level+1);
rt[level].push_back(nd->val);
dfs(nd->right, rt, level+1);

top Created with Sketch.