<p>Given the <code>root</code> of a binary tree, return <em>the inorder traversal of its nodes&#39; values</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">root = [1,null,2,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">[1,3,2]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png" style="width: 200px; height: 264px;" /></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">root = [1,2,3,4,5,null,8,null,null,6,7,9]</span></p>

<p><strong>Output:</strong> <span class="example-io">[4,2,6,5,7,1,3,9,8]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/29/tree_2.png" style="width: 350px; height: 286px;" /></p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">root = []</span></p>

<p><strong>Output:</strong> <span class="example-io">[]</span></p>
</div>

<p><strong class="example">Example 4:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">root = [1]</span></p>

<p><strong>Output:</strong> <span class="example-io">[1]</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 100]</code>.</li>
	<li><code>-100 &lt;= Node.val &lt;= 100</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Recursive solution is trivial, could you do it iteratively?
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode* prev = nullptr, *current = root;
        vector<TreeNode*> parents;
        bool done = root == nullptr;

        while(!done)
        {
            if(!prev)
            {
                if(current->left)
                {
                    parents.push_back(current);
                    current = current->left;
                }
                else if(current->right)
                {
                    result.push_back(current->val);

                    parents.push_back(current);
                    current = current->right;
                }
                else
                {
                    result.push_back(current->val);

                    if(parents.size())
                    {
                        prev = current;
                        current = parents.back();
                        parents.pop_back();
                    }
                    else
                    {
                        done = true;
                    }
                }
            }
            else
            {
                if(prev == current->left)
                {
                    result.push_back(current->val);

                    if(current->right)
                    {
                        parents.push_back(current);
                        current = current->right;
                        prev = nullptr;
                    }
                    else
                    {
                        if(parents.size())
                        {
                            prev = current;
                            current = parents.back();
                            parents.pop_back();
                        }
                        else
                        {
                            done = true;
                        }
                    }
                }
                else if(prev == current->right)
                {
                    if(parents.size())
                    {
                        prev = current;
                        current = parents.back();
                        parents.pop_back();
                    }
                    else
                    {
                        done = true;
                    }
                }
            }
        }

        return result;
    }
};
9800