Clear recursion solution with C++ using DFS


  • 0
    M
    1. get the maxDepth costed O(logn)
    2. DFS traverse the tree
    3. if the depth is even, insert the ret[depth] front.
    4. else insert the ret[depth] end
    class Solution {
    public:
        int maxDepth(TreeNode *root){
            if (!root) return 0;
            return max(maxDepth(root->left), maxDepth(root->right))+1;
        }
        void recZigzagLevelOrder(TreeNode* root, int depth, vector<vector<int>> &ret){
            if (!root) return ;
            
            if (depth&1){
                ret[depth].insert(ret[depth].begin(), root->val);
            }
            else{
                ret[depth].push_back(root->val);
            }
            recZigzagLevelOrder(root->left, depth+1, ret);
            recZigzagLevelOrder(root->right, depth+1, ret);
        }
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            int depth = maxDepth(root);
            vector<vector<int>> ret(depth);
            recZigzagLevelOrder(root, 0, ret);
            return ret;
        }
    };
    

Log in to reply
 

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