How to improve my code in C++? It is kind of clumsy.


  • 0
    C
    vector<int> inorderTraversal(TreeNode *root) {
            vector<int> output;
            if (root == NULL)
               return output;
            stack <TreeNode *> nodeStack;
            TreeNode *current;
            nodeStack.push(root);
            current = root;
            while(1)
    		{
    
    		while(current->left){ // checking to the left;
    			nodeStack.push(current->left);
    			current = current->left;
    		}
    
                   TreeNode *node = nodeStack.top(); // the top one on the stack;
    		output.push_back(node->val); // get the value in the node;
    		nodeStack.pop();
    
    		     if(node->right){
    		       nodeStack.push(node->right);
    		       current = node->right;
    		     }
    			 else{
    				 if (nodeStack.empty() == true) return output;
    				 while(!nodeStack.top()->right){
    				 TreeNode *node = nodeStack.top(); // the top one on the stack;
    		                 output.push_back(node->val); // get the value in the node;
    				 nodeStack.pop();
    				 if (nodeStack.empty() == true) return output;
    				 }
    				 TreeNode *node = nodeStack.top(); // the top one on the stack;
    		                  output.push_back(node->val); // get the value in the node;
    				 current =  nodeStack.top()->right;
    				 nodeStack.pop();
    				 nodeStack.push(current);
    			 }
    		}
    }
    

    The code has been accepted by OJ. The whole procedure is inspired by a standard iterative version of "Binary Tree Preoder Traversal". By using stack, it is easy to form the iterative method. Hoping somone could improve my version of "Inorder Traversal", making it more neat.


  • 0
    F

    It's actually pretty simple if you think about how the stack trace from recursion works. Here's my solution:

    class Solution {
    public:
        vector<int> order;
        vector<int> inorderTraversal(TreeNode *root) {
            addNextNode(root);
            return order;
        }
        void addNextNode(TreeNode* node) {
            if (node) {
                addNextNode(node->left);
                order.push_back(node->val);
                addNextNode(node->right);
            }
        }
    };

  • 0
    S

    But that's recursive, the whole point is to avoid recursion.


  • 0
    S

    I'm not sure if you want to see a better solution, or to get hints on how to write one yourself.

    One thing that would help is to have fewer TreeNode* variables. My solution only has one, yours has five. You can combine some of them just by increasing their scope.

    You have some conditions that are repeated, which can be combined.

    You don't need to push every right child onto the stack. What needs to go on the stack are the nodes that you must return to, which are only nodes that have left children.


Log in to reply
 

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