0 ms c++ solution, iterative


  • 1
    A
    /**
     * 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) {
            vector<int> a;
            stack<TreeNode*> s;
            if(root == NULL) return a;
            
            go(root,a,s);
        
            return a;
        }
        
        void go(TreeNode* t,vector<int> &a, stack<TreeNode*> &s) {
            while (1) {
                 // find leftest node
                 while (1) {
                     if (t != NULL) s.push(t);
                     else break;
                     if (t->left != NULL) t = t->left;
                     else break;
                 }
                 
                 if (s.empty()) return;
                 t = s.top();
                 s.pop();
                 a.push_back(t->val);
                 
                 // find node with right child in first node poped from stack 
                 t = t->right;
                 while (t == NULL) {
                     if (s.empty()) return;
                     t = s.top();
                     a.push_back(t->val);
                     t = s.top()->right;
                     s.pop();
                 }
                 
              
            }
            
        }
    };
    

Log in to reply
 

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