二叉树的中序遍历

利用栈实现中序遍历，先遍历到左子树最深处并将路径节点入栈，弹出栈顶节点（根）记录值，再遍历其右子树，重复该过程直至所有节点处理完毕。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk; // 存储遍历路径的节点
        vector<int> ans;      // 存储中序遍历结果
        
        // 栈非空或当前节点非空，继续遍历
        while(!stk.empty() || root != nullptr){
            // 遍历到左子树最深处，沿途节点入栈
            while(root != nullptr){
                stk.push(root);
                root = root->left;
            }
            // 弹出栈顶（根）
            root = stk.top();
            stk.pop();
            ans.push_back(root->val); // 记录根节点值
            root = root->right;       // 遍历右子树
        }
        return ans;
    }
};

时间复杂度： O(n) 空间复杂度： O(n)