What have I ignored in my algorithm for "Binary Tree Preorder Traversal"?


  • 0
    L

    what's wrong with my solution? I consider it as just a simple BTS,
    however it was wrong when I met the case [1 4 3 2], ouput [1 4 3 2] by my solution and experted [1 4 2 3].
    So can some one kindly tell me what I've ignored in understanding the question.? I'm a beginner in algorithm.
    Thanks.

     class Solution {
        public:
            // BTS?
            vector<int> preorderTraversal(TreeNode *root) {
                vector<int> ret = vector<int>();
                if(root == NULL){
                        
                    return ret;
                }
                queue<TreeNode *> qt = queue<TreeNode *>();
            	qt.push(root);
            	while(!qt.empty()){
            		TreeNode * tn = qt.front();
            		qt.pop();
            		ret.push_back(tn->val);
            		if(tn->left!=NULL){
            			qt.push(tn->left);
            		}
            		if(tn->right!= NULL){
            			qt.push(tn->right);
            		}
            	}
            	return ret;
                    
                
                
            }
        };

  • 0
    M

    The problem in your algorithm is that the simple method uses a stack, not a queue.
    With both methods, you pop the root, then push its left and right children. The problem arises after you pop the left child. You add the left's children to the queue, but the right child is still there, and comes before the left's children as it was added first.

     class Solution {
        public:
            // BTS?
            vector<int> preorderTraversal(TreeNode *root) {
                vector<int> ret = vector<int>();
                if(root == NULL){
    
                    return ret;
                }
                stack<TreeNode *> qt = stack<TreeNode *>();
                qt.push_back(root);
                while(!qt.empty()){
                    TreeNode * tn = qt.top();
                    qt.pop_back();
                    ret.push_back(tn->val);
                    if(tn->right!= NULL){
                        qt.push_back(tn->right);
                    }
                    if(tn->left!=NULL){
                        qt.push_back(tn->left);
                    }
                }
                return ret;
            }
        };
    

    Your algorithm:

    root->l,r->r,ll->ll->0
    

    Stack algorithm:

    root->r,l->r,ll->r->0
    

  • 0
    R

    Your program is performing "breadth-first traversal". However in this case you're expected to do "depth-first traversal" (preorder implicitly means depth first). Please check wiki for the difference between traversal types and it'll become clearer.


Log in to reply
 

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