C++ recursive & non-recursive solutions


  • 2
    B

    recursive solution

    /**
     * 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> result;
        
        vector<int> inorderTraversal(TreeNode* root) {
            
            dfs(root);
            return result;
        }
        void dfs(TreeNode *root){
            if(!root) return;
            dfs(root->left);
            result.push_back(root->val);
            dfs(root->right);
        }
    };
    

    non-recursive solution

    /**
     * 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*> stk;
            vector<int> result;
            TreeNode *p=root;
            
            if(!root) return result;
            
            while(p){
                stk.push(p);
                p=p->left;
            }
            
            while(!stk.empty()){
                p=stk.top();
                result.push_back(p->val);
                stk.pop();
                
                if(p->right){
                    p=p->right;
                    while(p){
                        stk.push(p);
                        p=p->left;
                    }
                }
    
            }
            return result;  
        }
       
    };
    

  • 0
    H

    good solution!


  • 0
    H

    I have added comments for this code
    // pseudocode
    // p = root;
    // while p is valid
    // p = p -> left and store p
    // then travel back,
    // if the p->right is valid
    // p = p -> left

    class Solution {
    public:
    vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> nodeStack;
    vector<int> result;
    TreeNode* p = root;
    if(!root) return result; // edge case
    // go to leftmost node first
    while(p)
    {
    nodeStack.push(p); // push the node into stack
    p = p->left;
    }
    // the search on the leftmost path is done
    // and at this point, p point into a null pointer
    // the next stage is too pop stack

    while(!nodeStack.empty())  // while the stack is not emmpty 
    {
        p = nodeStack.top();    // redirect p to point the top element 
        result.push_back(p->val); // push the value of the node
        nodeStack.pop();          // pop the accessed node
        // at this point, we need to check if there is right node adjacent to this ndoe
        if(p->right) // if it is,we need to do a lefmost search 
        {
            p = p->right;
            while(p)  // do a lefmost search
            {
                nodeStack.push(p);
                p = p->left;
            }
        }
    }
    

    return result;
    }

    };

    • list item

Log in to reply
 

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