Какова трудная временная сложность этого алгоритма для обхода порядка бинарного дерева по зигзагообразному уровню?

Обход уровня бинарного дерева по зигзагообразному уровню
Для заданного бинарного дерева верните зигзагообразный обход порядка значений его узлов.
(т.е. слева направо, затем справа налево для следующего уровня
и наоборот).

Например: Дано двоичное дерево {3,9,20, #, #, 15,7},

        3
/ \
9   20
/ \
15   7

вернуть его прохождение порядка зигзагообразного уровня как:

[
[3],
[20,9],
[15,7]
]

---

Лично я считаю,
сложность времени = O (n * высота), n — количество узлов, высота — высота данного двоичного дерева.

   getHeight()             => O(n)
traverseSpecificLevel() => O(n)
reverseVector()         => O(n)
swap()                  => O(1)

---

C ++

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#include <vector>
using namespace std;

class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> list;

// Input validation.
if (root == NULL) return list;

// Get the height of the binary tree.
int height = getHeight(root);

bool left_to_right = true;
for (int level = 0; level <= height; level ++) {
vector<int> subList;
traverseSpecificLevel(root, level, subList);

if (left_to_right == true) {
// Add subList into list.
list.push_back(subList);
// Update left_to_right flag.
left_to_right = false;

} else {
// Reverse subList.
reverseVector(subList);
// Add reversed subList into list.
list.push_back(subList);
// Update left_to_right flag.
left_to_right = true;
}
}
return list;
}

int getHeight(TreeNode *root) {
// Base case.
if (root == NULL || (root->left == NULL && root->right == NULL)) return 0;
else return 1 + max(getHeight(root->left), getHeight(root->right));
}

void traverseSpecificLevel(TreeNode *root, int level, vector<int> &subList) {
// Base case.
if (root == NULL) return;
if (level == 0) {
subList.push_back(root->val);
return;
}

// Do recursion.
traverseSpecificLevel(root->left, level - 1, subList);
traverseSpecificLevel(root->right, level - 1, subList);
}

void reverseVector(vector<int> &list) {
// Input validation.
if (list.size() <= 1) return;

int start = 0;
int end = list.size() - 1;
while (start < end) {
swap(list, start, end);

start ++;
end --;
}
}

void swap(vector<int> &list, int first, int second) {
int tmp = list[first];
list[first] = list[second];
list[second] = tmp;
}
};