94. 二叉树的中序遍历

问题描述

给定root，返回中序遍历，答案格式：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        
    }
};

则：

1. 将vector作为static或者全局变量，可以在该函数中实现递归；
2. 写另外一个函数专门用来递归；

法一、使用另外的递归函数

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

法二、使用全局变量

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;
    }
};

如果使用static，且不用另外的递归函数，会导致下一个测试用例中带有本次测试用例的答案，从而只有第一个测试用例正确，错误代码如下：

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

此外，可以使用递归，则也可以使用栈来解决。对于官方题解，比较麻烦，根据其他用户的题解，可以使用染色法，将未访问过的结点记为WHITE，访问过的结点记为GRAY，该方法容易实现，且可拓展性强，C++实现如下。

法三、栈+染色法

class Solution {
public:
    vector<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        const int GRAY = 1; // 已经访问过
        const int WHITE = 0;
        stack<pair<TreeNode*, int>> st;
        st.push(make_pair(root, WHITE));
        while(!st.empty()) {
            TreeNode* p = st.top().first;
            int status = st.top().second;
            st.pop();
            if (p == nullptr) {
                continue;
            }
            if (status == WHITE) {
                st.push(make_pair(p->right, WHITE));
                st.push(make_pair(p, GRAY));
                st.push(make_pair(p->left, WHITE));
            } else {
                res.push_back(p->val);
            }
        }
        return res;
    }
};

也可以利用该方法实现前序和后序遍历。