An clean C++ solution using a tag variable


  • 0
    H

    '''
    /**

    • Definition for a binary tree node.

    • 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* > node_stack;
      vector<int> res;

       if ( root == NULL ) return res;
       
       bool should_pop = 0;
       node_stack.push(root);
       while ( !node_stack.empty() ) {
           TreeNode* node = node_stack.top();
           
           if ( node->left == NULL || should_pop ) {
               res.push_back(node->val);
               node_stack.pop();
               should_pop = 1;
               if ( node->right != NULL ) {
                   node_stack.push(node->right);
                   should_pop = 0;
               }
           }
           else {
               node_stack.push(node->left);
           }
       }
       return res;
      

      }
      };
      '''


Log in to reply
 

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