Clear recursion solution with C++ using DFS

  • 0
    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 {
        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);
            recZigzagLevelOrder(root->left, depth+1, ret);
            recZigzagLevelOrder(root->right, depth+1, ret);
        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.