二叉树的中序遍历-c++两种方式-牛客BM24

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 0≤n≤1000，树上每个节点的值满足0≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector ans;
        if(root == NULL) return ans;
        inorder(root, ans);
        return ans;
    }
    void inorder(TreeNode* root, vector& ret){
        if(root == NULL) return;
        inorder(root->left, ret);
        ret.emplace_back(root->val);
        inorder(root->right, ret);
    }
};

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector ans;
        if(root == NULL) return ans;
        stack st; //辅助数组
        TreeNode* p = root;
        while(p || !st.empty()){
            while(p){
                st.push(p);
                p = p->left;
            }
            if(!st.empty()){
                p = st.top();
                st.pop();
                ans.emplace_back(p->val); //与前序遍历的不同之处
                p = p->right;
            }
        }        
        return ans;
    }
};