题目描述

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

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        auto p = root;
        while(p ||stk.size())
        {
            while(p)//是一个树，有左或右 的子树。
            {
                stk.push(p);
                p=p->left;//这里直接把所有左树走到头，后面只用看右树，右树也会走到这里看自己的左树。
            }
            p=stk.top();//往回返一下，返到根节点，在后面回去找右子树。
            stk.pop();
            res.push_back(p->val);
            p = p->right;
        }
};