Why my code leave an element[2] in the tree {3,1,#,#,2}


  • 0
    H
    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root) 
        {
            stack<TreeNode *> s;
            TreeNode *pRoot=root;
            vector<int> vNode;
            
            while(NULL!=pRoot || !s.empty())
            {
                while(NULL!=pRoot)
                {
                    s.push(pRoot);
                    pRoot=pRoot->left;
                }
                
                while(!s.empty())
                {
                    pRoot=s.top();
        //        cout << pRoot->val << endl;
                    vNode.push_back(pRoot->val);
                    s.pop();
                    pRoot=pRoot->right;
                }
            }
            
            return vNode;
        }
    };
    
    
    and the wrong info is as bellow:
    
    //    Input: 	{3,1,#,#,2}
    //    Output: 	[1,3]
    //    Expected: 	[1,2,3]

  • 0
    S

    why do you add while(!s.empty()) in the inner while? since you have judged that this stack is empty or not before you entering this while, there is no need to add this during the while. You have to only popup this stack and get the root node. Please delete while(!s.empty()) and you will get the wright answer.


  • 1
    G

    It is because, although you are visiting the right child "3", you are not processing it or its children. When you are traversing, at one point during execution, pRoot=pRoot->right points to the node 3. But, because the stack is not empty, the inner while loop does not terminate and hence, pRoot=s.top();. Therefore, no processing was done with node 3 and it was just lost.

    One of the best solutions to this problem would be to replace both the inner while statement with if statements or if-else statements. Your solution is near perfect otherwise.


Log in to reply
 

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