Use stack, but slightly different solution than I saw in the forum


  • 0
    H

    This is not using the 'curr' pointer, but using the order in the stack to identify when to put the node into the answer list

     * 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> v;
            stack<TreeNode*> s;
            s.push(root);
            while (!s.empty()) {
                TreeNode* curr=s.top();
                s.pop();
                if (!curr) continue;
                if (!s.empty() && curr->right==s.top()) {
                    v.push_back(curr->val);
                } else {
                    s.push(curr->right);
                    s.push(curr);
                    s.push(curr->left);
                }
            }
            return v;
        }
    };```

Log in to reply
 

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