题目描述

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

示例:

样例

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

自己常用的一个代码模板，提供不一样的写法，如果觉得这个风格适合自己可以背一背

C++ 代码

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        //迭代算法
        stack<TreeNode*> st;
        while(st.size() || root) //如果root为nullptr，，st里面百分百不为空 
        {                         //在后面else之后不需要再进行判断为空
            if(root)
            {
                st.push(root);
                root = root->left;
            }else{ //root已经往左走到头，取出最左边的值放入数组，
                    //然后进入右子树，并且尝试继续往左走
                root = st.top();
                res.push_back(root->val);
                root = root->right;
                st.pop();
            }
        }
        return res;
    }