{"id":5473,"date":"2019-08-20T22:10:56","date_gmt":"2019-08-21T05:10:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5473"},"modified":"2019-08-20T22:19:27","modified_gmt":"2019-08-21T05:19:27","slug":"leetcode-103-binary-tree-zigzag-level-order-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-103-binary-tree-zigzag-level-order-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 103. Binary Tree Zigzag Level Order Traversal"},"content":{"rendered":"\n

Given a binary tree, return the zigzag level order<\/em> traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).<\/p>\n\n\n\n

For example:
Given binary tree [3,9,20,null,null,15,7]<\/code>,
<\/p>\n\n\n\n

    3\n   \/ \\\n  9  20\n    \/  \\\n   15   7\n<\/pre>\n\n\n\n
return its zigzag level order traversal as:
<\/p>\n\n\n\n
[\n  [3],\n  [20,9],\n  [15,7]\n]<\/pre>\n\n\n\n
Solution 1: DFS<\/strong><\/h2>\n\n\n\n
in order traversal using DFS and reverse the result of even levels.<\/p>\n\n\n\n
Time complexity: O(n)
Space complexity: O(n)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua, 0ms, 15.1 MB\nclass Solution {\npublic:\n  vector > zigzagLevelOrder(TreeNode *root) {\n    vector> ans;\n    function dfs = [&](TreeNode* r, int d) {\n      if (!r) return;\n      while (ans.size() <= d) ans.push_back({});      \n      ans[d].push_back(r->val);      \n      dfs(r->right, d + 1);\n      dfs(r->left, d + 1);\n    };\n    dfs(root, 0);    \n    for (int i = 0; i < ans.size(); i += 2)\n      reverse(begin(ans[i]), end(ans[i]));      \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
Solution 2: BFS<\/strong><\/h2>\n\n\n\n
Expend\/append in order for even levels and doing that in reverse order for odd levels.<\/p>\n\n\n\n
Time complexity: O(n)
Space complexity: O(n)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector> zigzagLevelOrder(TreeNode *root) {\n    if (!root) return {};\n    vector> ans;\n    deque q;\n    q.push_back(root);\n    int d = 0;\n    while (q.size()) {\n      ans.push_back({});    \n      auto cur = &ans.back();\n      deque next;\n      while (q.size()) {\n        if (d % 2) {\n          TreeNode* node = q.back();\n          q.pop_back();\n          cur->push_back(node->val);\n          if (node->right) next.push_front(node->right);\n          if (node->left) next.push_front(node->left);          \n        } else {\n          TreeNode* node = q.front();\n          q.pop_front();\n          cur->push_back(node->val);\n          if (node->left) next.push_back(node->left);\n          if (node->right) next.push_back(node->right);          \n        }\n      }\n      ++d;\n      q.swap(next);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
Related Problems<\/strong><\/h2>\n\n\n\n