C++ solution using stack with explanation


  • 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) {
            vector<int> result;
            if(root == NULL) {
                return result;
            }
            
            vector<TreeNode*> nodeStack;
            TreeNode* node = root;
            
            nodeStack.push_back(node);
            node = node->left;
            
            while(!nodeStack.empty() || node != NULL) {
                //walk through left child node at first
                if(node != NULL) {
                    nodeStack.push_back(node);
                    node = node->left;
                }
                else {
                    //if there is no left child anymore, pop up current top node and add it to result
                    node = nodeStack.back();
                    nodeStack.pop_back();
                    result.push_back(node->val);
                    
                    //if node stack is not empty, and there is no right child for current node, then continue
                    // to pop up the nodes from stack
                    //otherwise, walk though right child of current node
                    if(!nodeStack.empty()) {
                        if(node->right != NULL) {
                            node = node->right;
                        }
                        else {
                            node = NULL;
                        }
                    }
                    else {
                        node = node->right;
                    }
                }
            }
            
            return result;
        }
    };

  • 0
    L
    /*I optimized your  code,it get accepted*/
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) 
    	{
            vector<int> result;
            if(root == NULL)
                return result;
            vector<TreeNode*> nodeStack;
            TreeNode* node = root;
            nodeStack.push_back(node);
            node = node->left;
            while(!nodeStack.empty() || node != NULL) 
    		{//walk through left child node at first
                if(node != NULL) 
    			{
                    nodeStack.push_back(node);
                    node = node->left;
                }
                else 
    			{//if there is no left child anymore, pop up current top node and add it to result
                    node = nodeStack.back();
                    nodeStack.pop_back();
                    result.push_back(node->val);
                    node = node->right;
                }
            }
            return result;
        }
    };

Log in to reply
 

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