LeetCode

Binary Tree Zigzag Level Order Traversal

2014.1.1 02:13

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

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.

Solution:

　　This problem is a variation from level-order traversal of binary tree, please see the reference here.

　　My solution is to get the level-order traversal first and reverse every other row to get the zig-zag version.

　　Time complexity is O(n), space complexity is O(1), where n is the number of nodes in the tree.

Accepted code:

 1 // 1AC, excellent!!
 2 /**
 3  * Definition for binary tree
 4  * struct TreeNode {
 5  *     int val;
 6  *     TreeNode *left;
 7  *     TreeNode *right;
 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9  * };
10  */
11 class Solution {
12 public:
13     vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
14         int i;
15         
16         for(i = 0; i < result.size(); ++i){
17             result[i].clear();
18         }
19         result.clear();
20         
21         if(root == nullptr){
22             return result;
23         }
24         
25         preOrder(root, 0);
26         
27         for(i = 0; i < result.size(); ++i){
28             if(i % 2){
29                 reverse(result[i], 0, result[i].size() - 1);
30             }
31         }
32         
33         return result;
34     }
35 private:
36     vector<vector<int>> result;
37     
38     void preOrder(TreeNode *root, int height) {
39         if(root == nullptr){
40             return;
41         }
42         while(result.size() <= height){
43             result.push_back(vector<int>());
44         }
45         result[height].push_back(root->val);
46         
47         if(root->left != nullptr){
48             preOrder(root->left, height + 1);
49         }
50         if(root->right != nullptr){
51             preOrder(root->right, height + 1);
52         }
53     }
54     
55     void reverse(vector<int> &num, int left, int right) {
56         int i;
57         
58         if(left >= right){
59             return;
60         }
61         
62         int tmp;
63         i = left;
64         while(i < left + right - i){
65             tmp = num[i];
66             num[i] = num[left + right - i];
67             num[left + right - i] = tmp;
68             ++i;
69         }
70     }
71 };