题目描述

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

样例

算法1

(递归) $O(n)$

C++ 代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        getmid(root, ans);
        return ans;
    }
    void getmid(TreeNode *root, vector<int> &ans){
        if(!root) return;

        if(root->left) getmid(root->left, ans);
        ans.push_back(root->val);
        if(root->right) getmid(root->right, ans);
    }
};

算法2

(迭代) $O(n)$

C++ 代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode *p = root;
        while(p || !st.empty()){ //判断栈 和 右子树
            while(p){
                st.push(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};