103. Binary Tree Zigzag Level Order Traversal

2019-11-06 08:50:26

字体：大中小

来源：转载

供稿：网友

问题描述 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]]

解决思路参考102题，我们只需要将队列变成栈就可以。但是这里需要考虑一个问题，就是想z型输出，相邻的两层之间的左右节点push的顺序也需要变换。

代码

/** * 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) { if (root == NULL) return vector<vector<int>>(); stack<TreeNode*> cur; stack<TreeNode*> next; cur.push(root); vector<vector<int>> result; vector<int> tmp; bool flag = false; while(!cur.empty() || !next.empty()) { if (!cur.empty()) { tmp.push_back(cur.top()->val); if (!flag) { if (cur.top()->left != NULL) next.push(cur.top()->left); if (cur.top()->right != NULL) next.push(cur.top()->right); } else { if (cur.top()->right != NULL) next.push(cur.top()->right); if (cur.top()->left != NULL) next.push(cur.top()->left); } cur.pop(); } else { cur = next; next = stack<TreeNode*>(); result.push_back(tmp); tmp = vector<int>(); flag = !flag; } } result.push_back(tmp); return result; }};

上一篇：492. Construct the Rectangle

下一篇：线程并行与并发的区别