My c++ 4ms solution with recursion


  • 0
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
     /* Each time we have 3 decisions to make:
        1. Whether the combination of this layer is created. If not, create one.
        2. IF 1. is true, then how to put the value of the root into the vector of this layer. We use dir to record the direction of the layer. dir = 0 means we search from left to right, and the left child is the first of the vector. Therefore we use insert, otherwise we use push_back.
        3. The priority of the next child to search. If (dir + 1) % 2 == 0, we search left child first, then right child. 
    */
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            int dir = 0, layer = 1;
            vector<vector<int>> result;
            helper(result, root, dir, layer);
            return result;
        }
        void helper(vector<vector<int>> &result, TreeNode *root, int dir, int layer) {
            if (!root) return;
            if (result.size() < layer) result.push_back(vector<int>(1, root->val));
            else {
                if (dir == 1) result[layer-1].push_back(root->val);
                else result[layer-1].insert(result[layer-1].begin(), root->val);
            }
            dir += 1;
            TreeNode *first = (dir == 0) ? root->left : root->right;
            TreeNode *second = (dir == 0) ? root->right : root->left; 
            helper(result, first, dir % 2, layer + 1);
            helper(result, second, dir % 2, layer + 1);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.