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,#,#,15,7},

3

/ \

9 20

/ \

15 7

return its zigzag level order traversal as:

[

[3],

[20,9],

[15,7]

]

confused what "{1,#,2,3}" means? >

read more on how binary tree is serialized on OJ.

Subscribe to see which companies asked this question

//递归方法：用一个bool记录是从左到右还是从右到左。每一层结束就翻转一下。

class Solution {

public:

vector> zigzagLevelOrder(TreeNode* root) {

vector> res;

traverse(root, 1, res, true);

return res;

}

void traverse(TreeNode* root, int level, vector> &res, bool left_to_right){

if (!root) return;

if (level > res.size())

res.push_back(vector());

if (left_to_right)

res[level - 1].push_back(root->val);

else

res[level - 1].insert(res[level - 1].begin(), root->val);

traverse(root->left, level + 1, res, !left_to_right);

traverse(root->right, level + 1, res, !left_to_right);

}

};

查看原文