leetcode

0 class Solution {

1 public:

2 vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

3 if (!root) return {};

4

5 vector<vector<int>> res;

6 queue<TreeNode *> q;

7 bool right = true;

8

9 q.push(root);

10 for (int lvl = 0; !q.empty(); lvl++) {

11 res.push_back(vector<int>());

12 for (int t = q.size(); t > 0; t--) {

13 TreeNode *root = q.front();

14 q.pop();

15 res[lvl].push_back(root->val);

16

17 if (root->left) q.push(root->left);

18 if (root->right) q.push(root->right);

19 }

20 if (!right) reverse(res[lvl].begin(), res[lvl].end());

21 right = !right;

22 }

23 return res;

24 }

25

26 vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

27 if (!root) return {};

28

29 vector<vector<int>> res;

30 deque<TreeNode *> d;

31 bool right = true;

32

33 d.push_front(root);

34 for (int lvl = 0; !d.empty(); lvl++, right = !right) {

35 res.push_back(vector<int>());

36 for (int t = d.size(); t > 0; t--) {

37 TreeNode *root;

38 if (right) {

39 root = d.front();

40 d.pop_front();

41 if (root->left) d.push_back(root->left);

42 if (root->right) d.push_back(root->right);

43 } else {

44 root = d.back();

45 d.pop_back();

46 if (root->right) d.push_front(root->right);

47 if (root->left) d.push_front(root->left);

48 }

49 res[lvl].push_back(root->val);

50 }

51 }

52 return res;

53 }

54 };