C++ 3ms DFS, Pre-Order Traversal, Recursive, Very Simple with Explanation


  • 0

    My Code Has 2 steps:

    • Step1: build ans vector with DFS
    • Step2: reverse odd rows so that they read from right to left

    Explanation

    • In Step1: Depth is the tree depth and the row of ans (which equal each other). Push each node onto ans and then traverse to left subtree (root->left), then right subtree (root->right).
      NOTICE: root->val, then root->left, then root->right is PREORDER Traversal, so the Entire left subtree is pushed onto ans before the right subtree and this is why every row reads from left to right before we do step 2.

    • In Step2: For each row of ans, if the row index is ODD, reverse that row so that the vertex read from right to left.

        private: vector<vector<int>>ans;
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
               buildvector(root,0); //STEP 1
               reverse_odd(ans);    //STEP 2
            return ans;
        }
        
        void buildvector(TreeNode* root, int depth){
            if(!root) return;
            if(ans.size()==depth)  ans.push_back(vector<int>());//ENTER ANOTHER ROW IN ans, SO CAN INDEX ans[depth]
            ans[depth].push_back(root->val); 
            buildvector(root->left,  depth+1); 
            buildvector(root->right, depth+1);
        }
        
        void reverse_odd(vector<vector<int>>& ans){
            for(int i=0; i<ans.size(); i++)
                if(i%2!=0)       //REVERSE ODD ROWS
                    reverse(ans[i].begin(),ans[i].end());
        }
    

Log in to reply
 

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