Nice'n easy using stack


  • 0
    W
    class Solution {
    public:
        vector<int> results;
        
        struct TreeNodeData
        {
            TreeNode* node;
            bool childrenAdded;
        
            TreeNodeData( TreeNode* i_node, bool i_childrenAdded ) : node(i_node), childrenAdded(i_childrenAdded) {
                
            }
        };
        
        stack< TreeNodeData > s;
    
        vector<int> inorderTraversal(TreeNode* root) {
            results.clear();
            
            if( root )
                s.push( TreeNodeData(root,false) );
            
            while( ! s.empty() ) {
                TreeNodeData nodeData = s.top();
                s.pop();
                
                if( nodeData.childrenAdded == false )
                {
                    s.push( TreeNodeData(nodeData.node, true));
                    
                    if( nodeData.node->left )
                        s.push( TreeNodeData( nodeData.node->left, false ) );
                }
                else
                {
                    results.push_back( nodeData.node->val );
                                    
                    if( nodeData.node->right )
                        s.push( TreeNodeData( nodeData.node->right, false ) );
                }
            }
                
            return results;
        }
    };

Log in to reply
 

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