# Leetcode 103. Binary Tree Zigzag Level Order Traversal
###### tags: `leetcode` `daily`

[題目連結](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/)

# Method DFS
:::info
:bulb: **作法講解**:
concept: using DFS algorithm preorder to solve this problem,

initialize vector<vector<int>> output store result,
traversal the tree from root node, level is 0,
traversal order is preorder,

for each node,
step 1, check output size if it's enough,
if output size == level, it means need add new vector.

step 2, add node's value into the back of output[level]

step 3, traverse the left child of the node.

step 4, traverse the right child of the node.

after traverse all of the node,
because the requirement is Zigzag Level Order Traversal,
we need to reverse the output,
we scan the level from 1 ~ n,
if level is odd, reverse the level of output.
:::

TC: O(N) SC: O(N)
:::spoiler 完整程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, int level, vector<vector<int>> &output) 
    {
        if(root == NULL) {
            return;
        }

        if(output.size() == level) {
            output.push_back({});
        }
        output[level].push_back(root->val);
        dfs(root->left, level+1, output);
        dfs(root->right, level+1, output);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> output;

        dfs(root, 0, output);
        
        for(int i = 1 ; i < output.size() ; i+=2) {
            reverse(output[i].begin(), output[i].end());
        }
        return output;
    }
};

:::