题目

94. 二叉树的中序遍历

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

输入：root = [1,null,2,3]
输出：[1,3,2]

思路(递归)

返回规定的是vector，那么我么中序遍历的时候向vector插入元素即可，注意要使用vector<int> &v

源代码

class Solution {
    
public:
    void midorver(TreeNode* root, vector<int> &v) {
    
        if (root != nullptr) {
    
            midorver(root->left, v);
            v.push_back(root->val);
            midorver(root->right,v);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
    
        vector<int> v;
        midorver(root,v);
        return v;
    }
};

思路（迭代）

利用栈模拟递归遍历

class Solution {
    
public:
    vector<int> inorderTraversal(TreeNode* root) {
    
        vector<int> v;
        stack<TreeNode*> s;
        while (root != nullptr || !s.empty()) {
     // 第一个包含了开始栈为空的特殊情况，且如果第一个为空指针，直接返回
            while (root != nullptr) {
     // 一直向左递归，知道节点为空
                s.push(root);
                root = root->left;
            }
            root = s.top();// 此时top，即为上个节点，相当于回溯上个节点
            s.pop();// 弹出
            v.push_back(root->val);// 保存元素
            root = root->right;// 去右子树遍历
        }
        return v;
    }   
};