二叉树的中序遍历

题目描述

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

输入输出样例

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

输出: [1,3,2]

题解

一、递归解法
根据中序遍历的顺序:左、中、右，使用递归的三步走，直接解题：

class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) return res;
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
        return res;
    }
};

二、迭代器解法
不同于前序与后序，它需要访问的元素与处理元素顺序是不一致的。那么在迭代写法中，我们就需要使用指针的遍历来访问节点，栈则用来处理节点上的元素。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> ans;
        TreeNode* node = root;
        while (node != nullptr || !ans.empty()) {
            if (node != nullptr) {
                ans.push(node);
                node = node->left;
            } else {
                node = ans.top();
                ans.pop();
                res.push_back(node->val);
                node = node->right;
            }
        }
        return res;
    }
};