花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

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

return its zigzag level order traversal as:

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

Solution 1: DFS

in order traversal using DFS and reverse the result of even levels.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 0ms, 15.1 MB

class Solution {

public:

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

vector<vector<int>> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* r, int d) {

if (!r) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(r->val);

dfs(r->right, d + 1);

dfs(r->left, d + 1);

};

dfs(root, 0);

for (int i = 0; i < ans.size(); i += 2)

reverse(begin(ans[i]), end(ans[i]));

return ans;

}

};

Solution 2: BFS

Expend/append in order for even levels and doing that in reverse order for odd levels.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

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

if (!root) return {};

vector<vector<int>> ans;

deque<TreeNode*> q;

q.push_back(root);

int d = 0;

while (q.size()) {

ans.push_back({});

auto cur = &ans.back();

deque<TreeNode*> next;

while (q.size()) {

if (d % 2) {

TreeNode* node = q.back();

q.pop_back();

cur->push_back(node->val);

if (node->right) next.push_front(node->right);

if (node->left) next.push_front(node->left);

} else {

TreeNode* node = q.front();

q.pop_front();

cur->push_back(node->val);

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

++d;

q.swap(next);

}

return ans;

}

};

花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

Solution 1: DFS

C++

Solution 2: BFS

C++

Related Problems

Be First to Comment

Leave a Reply Cancel reply