LeetCode 94. 二叉树的中序遍历 C++

LeetCode 94. 二叉树的中序遍历 C++

方法：

1.迭代

2.递归

详细思路见注释

class Solution {
public:
    // 思路：
    // 1. 将整棵树的最左边一条链压入栈中
    // 2. 每次取出栈顶元素，如果它有右子树，则将右子树压入栈中
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;// 存储结果
        stack<TreeNode*> stk;

        auto p = root;
        // 当p不为空或者stk中有元素，循环继续
        while (p || stk.size()){
            while (p){// 将最左边的链压入栈中
                stk.push(p);
                p = p->left;
            }
            p = stk.top();// 将p赋值为栈顶的元素，即最左边链的最下面的元素
            stk.pop();// 然后将栈顶元素弹出
            res.push_back(p->val);// 存放一个结果
            p = p->right;// 再将p的右子树的最左边链压入栈中
        }
        return res;
    }

    
    /*
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(ans, root);

        return ans;
    }

    void inorder(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
        {
            return;
        }
        inorder(ans, root->left);
        ans.push_back(root->val);
        inorder(ans, root->right);
    }
    */


};